Question
Given a list of numbers, where every number shows up twice except for one number, find that one number.
Example:
Input: [4, 3, 2, 4, 1, 3, 2]
Output: 1
Here’s the function signature:
def singleNumber(nums):
# Fill this in.
print (singleNumber([4, 3, 2, 4, 1, 3, 2]))
# 1
Solution 1: Using a hash map
Solution 2: Using Xor
The challange was to try and do it using O(1) memory. Meaning just one more variable change.
The best solution in this situation is to use XOR. Performing XOR for all array elements gives us the number with single occurrence.
Explaination:
a) XOR of a number with itself is 0.
b) XOR of a number with 0 is number itself.
b) XOR of a number with 0 is number itself.
arr = [4, 3, 2, 4, 1, 3, 2] – Let’s take these and perform a dry run for the following code
res = arr[0]
for i in range(1,len(arr)):
res = res ^ ar[i]
1st loop:
res = 4
res = 4 XOR 3 = 7
2nd loop:
res = 7
res = 7 XOR 2 = 5
3rd Loop:
res = 5
res = 5 XOR 4 = 1
.
.
.
1 XOR 1 = 0
0 XOR 3 = 3
3 XOR 2 = 1
Final answer = 1
To learn more about XOR – click here
To calculate your own test cases for XOR – click here
Where else can you use XOR in this fashion ?
Try using it to find one element that occurs odd number of times in an array.
