The 2nd Codility lesson is to search for the odd number of elements in an array that cannot be paired with any other element. Codility provided this example.
A[0] = 9, A[1] = 3, A[2] = 9
A[3] = 3, A[4] = 9, A[5] = 7
A[6] = 9
Apart from A[5], every other element has a match. The first thought is to iterate through the array and look for the pair and remove both elements once it is found. When an element cannot find its pair, break from the loop and return the element. Simple enough, so I coded.
It works for a small number of elements but Codility needs this to run in less than 1 second when tested in big random sets with 999,999 elements. My solution runs in time for only tests with 2,001 elements or less.
And this become a revision for bitwise operators after reading the comments in Codility. This was the final answer, adapted from what another programmer shared.
function solution(A) {
var i;
var ans = 0;
for (i = 0; i < A.length; i++)
{
ans = ans ^ A[i];
}
return ans;
}A review of bitwise operator XOR:
Bitwise operator XOR outputs true when input differs. So:
1 XOR 1 = 0
0 XOR 0 = 0
1 XOR 0 = 1
0 XOR 1 = 1
And when you walk through set of elements provided, this is the result, a really elegant solution that runs in 0.604 seconds for a set of 999,999 random numbers!
A[0] = 9 1001 XOR 0000 = 1001 (9)
A[1] = 3 0011 XOR 1001 = 1010 (10)
A[2] = 9 1001 XOR 1010 = 0011 (3)
A[3] = 3 0011 XOR 0011 = 0000 (0)
A[4] = 9 1001 XOR 0000 = 1001 (9)
A[5] = 7 0111 XOR 1001 = 1110 (14)
A[6] = 9 1001 XOR 1110 = 0111 (7)
So what really happened is that the numbers starts to cancel each other out. Remember, every 0 that hits another 0 becomes 0 and every 1 that hits another 1 becomes 0 too. At some point, the twin of a number is found and the same number will cancel itself out. Eventually only the odd number that doesn’t have a pair is left.
Photo by Adrian Curiel on Unsplash