Odd Occurrences In Array

Lately I have been doing a lot of code challenges and exercises. It is a great way to improve your coding abilities, but also to make better decisions. There are often concise way to do things and one challenge in particular was a good example of this.

Lets set the scence.

You have an array of numbers with a range of [1..1,000,000,000].

const A = [4,3,4,2,3]

We need to write a function that will return the odd value in the most effecient way and the best one I could find was the following:

function solution(A) {
    let result = 0;
    for (let element of A) {
        result ^= element
    }
    return result
}

While this is the correct solution, it doesn’t really explain what is going on.

When the function runs, it sets the results variable to 0 and then runs the for loop.

Each iteration of the for loop is performing an XOR (eXclusive OR) (^) bitwise operation with the XOR assignement operator (^=) which means the result of the right operand is assigned to the left operand once the operation is complete.

Take the following numbers and their binary representation.

According to MDN – Bitwise XOR returns a 1 in each bit position for which the corresponding bits of either but not both operands are 1s.

So for each bit position, the question asked is, are either numbers 1 but not both? If so, set the result to 1.

4 = 00000100
3 = 00000011
R = 00000111 = 7

In the above example, the last 3 bit positions have a 1 in either positions, but not both. So the result has its last 3 bit positions equal to 1. 00000111 is the binary representation of the number 7 which is then used to XOR with the next decimal number in our array which is 4. (7 ^ 4) = 3 and so on.

Each iteration in our for loop will take value of result which is 0 and XOR it with the next item in our array which starts with 4.

Using what you know above, look at the original Array and the table and you should begin to see the pattern.

const A = [4,3,4,2,3]

This gives us the final result which is 2. You can shift the numbers around and try it again, the result will still be 2.