Gamified challenge · XOR tricks
socks[i] is the colour code of sock i, a whole number from 0 to 1000. Every colour appears an even number of times (it comes in pairs) except one colour, which has a single extra sock with no partner.
Write lonely(socks) that returns the lonely sock's colour. For [4, 1, 2, 1, 2] the answer is 4.
Try to do it in one pass with O(1) extra memory: no set, no map, no sorting. Hint: a ^ a == 0 and a ^ 0 == a.
This game is part of the paid plans. Sign in, then pick a plan to write your answer, watch it play out, and step through the algorithm with its guide.
Sign in with Google