XOR: remember odd occurrences
Picture
x XOR x is zero, and x XOR 0 is x. Pairing equal values removes them regardless of order.
Predict
Would ordinary XOR find one unique value if others appear three times?
Walk through the small example
No. Associativity, commutativity, and self-cancellation remove all paired values.
Mental model and complete Python solution
XOR is a parity ledger for every bit. Seeing the same value twice toggles all of its bits on and then off; the unpaired value remains.
What the function promises: Return the unique integer under the exactly-one-singleton, all-others-twice contract.
def single_number(values):
answer = 0
for value in values:
answer ^= value
return answer
assert single_number([4,1,4]) == 1
assert single_number([-2,5,5]) == -2Work and storage: O(n) time and O(1) machine words.
When to recognize it: Associativity, commutativity, and self-cancellation remove all paired values.
Check before applying it: The result is meaningless for a different frequency contract unless the bit-state logic is redesigned.
Change one rule
Every repeated value appears three times.
See what changes
Count each bit modulo three with explicit width, or maintain bitwise finite-state masks.
Connect
Bits: tiny yes-or-no switches: XOR toggles each bit independently.
invariants: The running XOR equals the parity summary of the prefix.