Approach 1: Using extra memory (hash table)
A rather straightforward approach to solve this question is traverse the list of elements and put their count in a map (number -> count). Then traverse the map and return the number whose count is only 1. But this solution will take up O(n) memory and two passes (one for traversing array, one for map). We can do better!
Approach 2: One pass, O(n) memory
Suppose the array is made up of 3 numbers a, b, c of which a, c are repeated twice. The sum of array becomes actualSum = a + a + b + c + c = 2*a + b + 2*c = 2*(a+b) + c. If all the numbers were repeated twice, the sum would be totalSum = 2*a+2*b+2*c = 2*(a+b+c). Note that totalSum - actualSum = c. So all we have to do is find the unique numbers in the array and the total sum of the array. We can use a set to store the unique numbers.
Python solution:
class Solution {
public int singleNumber(int[] nums) {
int sumOfSet = 0, sumOfNums = 0;
Set<Integer> set = new HashSet();
for (int num : nums) {
if (!set.contains(num)) {
set.add(num);
sumOfSet += num;
}
sumOfNums += num;
}
return 2 * sumOfSet - sumOfNums;
}
}
We have reduced the number of passes (note that time complexity still remains O(n)) but the solution still takes up some memory. Although this solution is enough for an interview, let’s go one step further and apply some math!
Approach 3: Bit Manipulation
We can make use of XOR operation (a XOR b = (a AND b') OR (a' AND b)) to solve the question. Concept:
- If we take XOR of zero and some bit, it will return that bit:
a XOR 0 = a - If we take XOR of two same bits, it will return 0:
a XOR a = 0
This tells us that a XOR a XOR b = (a XOR a) XOR b = 0 XOR b = b. So all we have to do is take the XOR of all the elements in the array and we’ll be left the element which is not repeated twice!
int singleNumber(vector<int>& nums) {
int n = 0;
for (int i=0; i<nums.size(); i++)
n=n^nums[i];
return n;
}
Time complexity: O(n) one pass Space complexity: O(1)