# All Repeating Except One

#### 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 na1a2..n numbers`
Output Format
`Non-repeating number`
Question Video
Constraints
`1 <= n <= 10^91 <= a1,a2.. <= 10^9 `
Sample Input
`523 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.

• Related Topics

Run

Run
Id Name