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
simply take xor of all the elements in the array,it will give the answer in one pass…
if the nujmber ocurring once is 0 then what
I think this will work only if it is a sorted array,else it will take O(n^2) time.
Nope, will work either ways.