Category: Easy
Problem
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
Follow up: Could you implement a solution with a linear runtime complexity and without using extra memory?
Examples
Example 1:
1 2 | Input: nums = [2,2,1] Output: 1 |
Example 2:
1 2 | Input: nums = [4,1,2,1,2] Output: 4 |
Constraints
1 <= nums.length <= 3 * 104-3 * 104 <= nums[i] <= 3 * 104- Each element in the array appears twice except for one element which appears only once.
Solution Approach
In this problem of Single number, we have to find a number from a list of numbers which appears only once.
By reading the problem alone we can have some intuition that we need to use some data structure. We will indeed use sets as that will make our job easier. We can also use XOR to make it even simpler. The problem is not significantly tough but the approaches mentioned here can be used in different types of problems. Let’s talk about these two approaches in detail below.
Using Sets
We can use the set data structure to solve the problem. Sets are used to store the values only once so we can leverage that property to our advantage. We will store the value when we first encounter and then when we encounter the same element once again, we will remove that from the set. In the end, we will have only one element which does not have its pair and hence our single number.
The space complexity of this approach is O(n) as we are using a set to store the elements. The time complexity is O(n) as we need to iterate through the array once.
To code this approach we will first initialize a HashSet. Then we iterate through the array elements and if the element is not present in the set, we will add the element. In case the element is already present, we will delete that element. Lastly, we will return the only element which remains in the set.
Using XOR operator
This problem is an ideal case to use the XOR(^) operator to find the solution. XOR operator compares two input bits and generates one output bit. If the bits are the same, the result is 0. In our case, if two numbers are the same it then the corresponding bits will also be the same hence it will cancel out. The only number remaining at the end is the single number that we need.
The time complexity is O(n) as we iterate through the array once. The space complexity is only O(1) as we need only an extra variable to store the XORed value which will be the answer.
Coming to the code, we have to declare a variable to store the intermediate and end result. We have to initialize that variable as 0. Now we loop through all the elements and perform the XOR operation. We have to store the values in the variable we initialized. In the end, we just return the same as the answer.
Solution code
Using Sets
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution { public int singleNumber(int[] nums) { HashSet<Integer> set = new HashSet<>(); for (int num : nums){ if (!set.contains(num)) set.add(num); else set.remove(num); } return (int) set.iterator().next(); } } |
Using XOR operator
1 2 3 4 5 6 7 8 9 | class Solution { public int singleNumber(int[] nums) { int result = 0; for (int num : nums){ result ^= num; } return result; } } |
For more Leetcode explained solutions visit Leetcode Solutions.
If you like capture the flag challenges visit here.
Check out my socials below in the footer. Feel free to ask any doubts in the comment section or contact me via the Contact page I will surely respond. Happy Leetcoding đŸ™‚