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 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.