Odd occurring element in an array

in code


I dug into the problem and discovered that any number XOR’d with itself an odd number of times equals zero, whilst an even number of times equals the number itself:

7 ^ 7 = 0
7 ^ 7 ^ 7 = 7

The trick here is:

  1. Numbers which appear in the array an even number of times will lead to an odd number of XORs, which leads to 0.
  2. Number which appear in the array an odd number of times will lead to an even number of XORs, which leads to the number.

So in [1, 1, 2, 2, 3, 3, 4]:

1 ^ 1 = 0
2 ^ 2 = 0
3 ^ 3 = 0
0 ^ 4 = 4

The solution:

function oddOccurring(array) {
    return array.reduce(xor);
}

function xor(previous, current) {
    return previous ^ current;
}

To test:

let a = [0, 1, 2, 3, 0, 1, 2];
oddOccurring(a); // 3


A Summer of Running

in running

Achill Half Marathon

in running


Your email address will not be published. Required fields are marked *