[Solution] Find the non-duplicate number

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.
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.

Leave a reply:

Your email address will not be published.

Site Footer

Sliding Sidebar

About Me

About Me

Hey, I am Thomas Ashish Cherian. What I cannot create, I do not understand.

Social Profiles