Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Example 1:
Input: nums = [2,2,1]
Output: 1
Example 2:
Input: nums = [4,1,2,1,2]
Output: 4
Example 3:
Input: nums = [1]
Output: 1
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.
My Solution
You can solve this problem by keeping track of the counts of each number in the array and return the number that occurs once. Doing it this way would have a time complexity of O(n) and space complexity would be O(n) as well to maintain the HashMap. However, we can do better. To solve this problem, we need to understand a property of the XOR operation. A number XORed with itself will be 0 and any number XORed with 0 is the same number. Furthermore, the order in which we XOR numbers together does not actually matter. Putting these ideas together, we can find the number that occurs only once by just XORing all the numbers together. The numbers that occur twice will just reduce to 0 while the number that occurs once will XOR with 0 to remain itself. This is the number we return.
Time complexity would be O(n) since we are iterating once through the array. Space complexity would be O(1) since we only require constant extra space.
class Solution {
public int singleNumber(int[] nums) {
int out = 0;
for (int n : nums) {
out ^= n;
}
return out;
}
}