**Write an algorithm to find out a number from an ****array of numbers where only one number occurs once and rest ****all occurs twice.**

**Note: Without using extra O(n) space and in O(n).**

XOR all the numbers ,you will get the number with single occurrence.

**How?**

XOR has these two properties,You can checkout the properties of XOR here.

- A (+) A = 0
- A (+) 0 = A
- A (+) B (+) C = A (+) C (+) B

Thus all the numbers with two occurrences will become 0 after XOR and Number with only one occurrence will remain.

Facebook Comments

mohd waseem says

simply take xor of all the elements in the array,it will give the answer in one pass…

gaurav says

if the nujmber ocurring once is 0 then what

Mozart says

I think this will work only if it is a sorted array,else it will take O(n^2) time.

nomad says

Nope, will work either ways.