1

Given a list of n integers, where every integer in the list exists twice, except for one element, which exist once in the list. For example,

[1 3 3 6 2 7 1 2 7]

I need to find a linear time O(n), and a constant space O(1) algorithm that returns the element which exists once in the list. In the above example, the algorithm should return 6. Note that the list is not provided by any certain order. (The order of the elements in the list is random).

I could solve this problem in O(n) linear time using a dictionary but unfortunately the dictionary requires O(n) space. Any ideas?

Traveling Salesman
  • 2,209
  • 11
  • 46
  • 83

2 Answers2

6

Solving this puzzle requires knowledge of a small trick: XOR-ing a number with itself even number of times results in zero. Moreover, you can XOR other numbers with a temporary result in between; the order does not matter.

Therefore, if you XOR all values in the array together, you would get the only number that is present in the array only once:

int res = 0;
for (int i = 0 ; i != array.size() ; i++) {
    res ^= array[i];
}
cout << res << endl;
Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
3

You can xor all the numbers in the list together. The result will be the unduplicated element.

Paul Hankin
  • 54,811
  • 11
  • 92
  • 118