Easy XOR Cancel Bit Manipulation
In plain English: Find the number that appears only once in an array where every other number appears exactly twice.
XOR is its own inverse: a ^ a = 0 and a ^ 0 = a. XORing all elements cancels pairs, leaving the unique element.
Prompt
Given an array where every element appears twice except one, find the one that appears only once.
Try to write it from scratch before scrolling down.
Solution
def single_number(nums):
result = 0
for x in nums:
result ^= x # pairs cancel: a ^ a = 0
return result
# Test: single_number([2,2,1]) == 1
# Test: single_number([4,1,2,1,2]) == 4