All Repeating Except One
1. You are given an array of numbers.Input Format
2. All numbers occur twice in the array except one.
3. You have to find that number by traversing only once in the array and without using any extra
space.
A number nOutput Format
a1
a2..
n numbers
Non-repeating numberQuestion Video
1 <= n <= 10^9Sample Input
1 <= a1,a2.. <= 10^9
5Sample Output
23 27 23 17 17
27
-
Editorial
The problem here deals with finding the non-repeating number in the input array wherein every other number repeats itself exactly twice. Here we will use the property of XOR to get our result.
The truth table of XOR clearly depicts that for same operands it returns 0 and for different operands it returns 1. So as 1 ^ 1 = 0 and 0 ^ 0 = 0 then 5 ^ 5 = 0101 ^ 0101 = 0000. One more thing to keep in mind is that XOR operator is cumulative in nature i.e., say 5 ^ 3 ^ 5 is same as 5 ^ 5 ^ 3.
Now coming back to our problem as we know that every number repeats twice except our desired number, this implies that the XOR of the number with itself will lead to zero, so if we take the XOR of the entire array then all the duplicates would get cancelled out and the one that will be remaining will be our desired result.
Time Complexity: O(n)
The time complexity for the function is linear as we are traversing on every element of the array.
Space Complexity: O(1)
The space complexity for the function is constant.
-
Asked in Companies
-
Related Topics