This is LeetCode #136: Single Number — the perfect introduction to XOR! 🔮
💡 Think of it like this: Everyone in a room has a twin — except ONE person. How do you find the loner? XOR is the magic trick: when you XOR a number with itself, it becomes 0. So twins cancel out, and only the loner remains!
XOR Properties (the magic rules):
a ^ a = 0 — Any number XOR itself = 0 (cancel out!)a ^ 0 = a — Any number XOR zero = itself💭 Your turn! Take what you learned above and write the code yourself. Struggling is part of learning! 🧠
Why this works: Since every number except one appears twice, all pairs cancel to 0 via XOR. The remaining number XORs with 0 and stays as itself. Beautiful! 🎨
def singleNumber(nums):
result = 0
for num in nums:
result ^= num # XOR everything together
return result # Only the single number survives!
# Time: O(n), Space: O(1) — can't do better than this!
singleNumber([4, 1, 2, 1, 2])
4