Odd Occurrences In Array

Code Challenges JavaScript

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.

DecimalBinary
000000000
400000100
300000011
400000100
200000010
300000011

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]
OperationBinary ComparisonBinary ResultResult
0 ^ 400000000
00000100
000001004
4 ^ 300000100
00000011
000001117
7 ^ 400000111
00000100
000000113
3 ^ 200000011
00000010
000000011
1 ^ 300000001
00000011
000000102

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.

Matthew Horne

Matthew is a web developer from the United Kingdom who taught himself PHP and JavaScript and never looked back. If you would like to hire me, shoot me an email.