All Repeating Except One
Try First, Check Solution later1. You should first read the question and watch the question video.2. Think of a solution approach, then try and submit the question on editor tab.3. We strongly advise you to watch the solution video for prescribed approach.
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
A number nOutput Format
Non-repeating numberQuestion Video
1 <= n <= 10^9Sample Input
1 <= a1,a2.. <= 10^9
23 27 23 17 17
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