All Repeating Except One

  Prev   Next

Try First, Check Solution later

1. 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.
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.
Input Format 
A number n
a1
a2..
n numbers
Output Format 
Non-repeating number
Question Video
Constraints 
1 <= n <= 10^9
1 <= a1,a2.. <= 10^9
Sample Input 
5
23 27 23 17 17
Sample Output 
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






Video Solution

Code Solution

Run
 
Run
Id Name