0

I found out recently that you can use this function on an array of integers to find the one number that appears an odd number of times using JavaScript.

array.reduce((a, b) => a ^ b);

[1, 2, 2].reduce((a, b) => a ^ b); // returns 1

I'm struggling to figure out how the XOR operation (^) works and am wondering if there is a similar function that can find a number that appears an even number of times in an array.

Zach Handler
  • 23
  • 5
  • `[1, 2, 3].reduce((a, b) => a ^ b);` returns 0, so probably not the best way to check for uniqueness. – Taplar Feb 10 '20 at 21:00
  • Remember that `reduce` takes a function with arguments `tally, currentelement`, calling them `a, b` is a good way to get confused, and it's an even better idea to also pass a starting value for the tally. – Mike 'Pomax' Kamermans Feb 10 '20 at 21:01
  • Also see [a](https://stackoverflow.com/questions/2644179/find-the-only-unpaired-element-in-the-array), [b](https://stackoverflow.com/questions/35185/finding-a-single-number-in-a-list), [c](https://stackoverflow.com/questions/29333689/how-to-find-the-only-number-in-an-array-that-doesnt-occur-twice), [d](https://stackoverflow.com/questions/4883630/algorithm-to-find-odd-item-with-no-pairs-in-an-array) – ggorlen Feb 10 '20 at 21:06

1 Answers1

1

XOR is a bit-wise operation where either of the comparison bits need to be 1 and the other 0 to result in a truthy value 1 (otherwise that's 0).

e.g.

10^12 = 

10 = 1010
12 = 1100
     ----
     0110 = 6
     ----

XOR Rules:
1 ^ 1 = 0 ^ 0 = 0
1 ^ 0 = 0 ^ 1 = 1

So, XOR of a number with itself gives 0. (Try it out.)

XOR of a number with 0 gives the number itself.

That means you're cancelling out all numbers which appear an even number of times. That leaves anything which does not occur an even number of times, XOR'ed with each other.

Ajit Panigrahi
  • 752
  • 10
  • 27
  • 1
    And it's important to observe that this is "basically, *just* a trick." If there was more than **one** "special number," or if any of the other values were not repeated **exactly twice,** this would not work. A more generalized approach which *does* work "generally" is to first **sort** the elements in the table. This places all identical values adjacent to one another, so the number of duplicates can be trivially determined. Modern sorting algorithms are very efficient, allowing this strategy ... which actually dates all the way back to punched-cards ... to work very well. – Mike Robinson Feb 10 '20 at 21:40
  • True, though the linked duplicate question should have better answers. I tried to convey that in the last line in my answer: "That leaves anything which does not occur an even number of times, XOR'ed with each other." – Ajit Panigrahi Feb 10 '20 at 21:42