Pattern visualizer
Single Number
XOR has two properties that make this a one-line trick: x^x = 0 (a number cancels itself out) and x^0 = x (XOR with nothing changes nothing), and XOR doesn't care about order. So if you XOR every number in the array together, every PAIR cancels to 0, and whatever's left over is the single number that never had a partner to cancel with. No extra memory needed to track counts. Animated on: nums = [4,1,2,1,2] — every number appears twice except one, find it.
XOR cancels every pair, leaving only the odd one out
time O(n)space O(1)step 1 / 7
4
[0]1
[1]2
[2]1
[3]2
[4]line 2
Start with result=0. XOR with 0 changes nothing, so this is a safe starting point.
Pseudocode
1FUNCTION singleNumber(nums):2 result = 03 FOR each n in nums:4 result = result XOR n5 END FOR6 RETURN result7END FUNCTION
← / → step · space play · Home restart