Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Example 1: Input: [2,2,1,3,4,3,5,4,5,] Output: 1 Example 2: Input: [4,1,2,1,2] Output: 4
You will be thinking it’s a very simple problem. What we all need to do is to take count of each distinct number and that number having count 1 will be our answer. We can achieve it by using a dictionary.
Time Complexity – 0(N)
Space Complexity – 0(N)
What if your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? It means you have to solve the problem in O(N) time complexity and constant space that means space complexity must be O(1).
Think of an approach before going into the post.
Let me tell you, have you ever heard of Bit Manipulation?
‘’ As the name suggests, it is a process of performing logical operations on bits to achieve the desired result.’’
To understand the bit manipulation let’s first have a look at Logical Bitwise Operators.
- AND (&)
- OR ( | )
- XOR (^)
- Left Shift (<<)
- Right Shift (>>)
In our particular problem, we will implement Bitwise XOR to get the desired result.
Properties of Bitwise XOR (^)–
- 0 ^ 0 = 0
- 0 ^ 1 = 1
- 1 ^ 0 = 1
- 1 ^ 1 = 0
If we observe the above operations we find that XOR of the same bits results in 0 and XOR of two different bit results into 1.
Now, Let’s have a look on some other examples –
- 1 ^ 1 ^ 1 ^ 1 = 0
- 2 ^ 2 = 0
- 1 ^ 1 ^ 2 = 2
- 2 ^ 3 ^ 4 ^ 3 ^ 2 = 4 (XOR operation is commutative and associative)
Now pause and observe the above examples very carefully.
So, If you observe carefully you will find that XOR of all those numbers appearing twice are being cancelled out and we are left with the number that appears only once. It clearly means if there are N numbers out of which N-1 numbers appears twice (or even number of times) and one number appear only once, then XOR of all numbers collectively results into that number which appears only once (See Examples 6, 7, 8) and as a result we will get our desired number.
As in example 8, 2 appears twice (so 2 ^ 2 = 0) and 3 appears twice (3 ^ 3 = 0) and 4 appears only once so as a consequence we will get 4 (0 ^ 0 ^ 4 = 4)
So in order to solve our particular problem we need to find XOR of all the numbers of array and and resultant XOR will be our answer.
Python Solution –
def singleNumber(Arr, n): ans=0 for i in range(N): ans^=Arr[i] return ans
- Iterate over all elements of array
- Find the XOR of all elements of array and store it into a variable ans.
- Return ans.
- Time Complexity – O(n)
- Space Complexity- O(1)
This article is contributed by Md Taslim Ansari