When to use it#
Look for the structural evidence below before naming the pattern. The constraints and invariant - not a keyword - make the choice defensible.
Recognition signals
- Parity
- Unique value
- Subset mask
When another approach fits better
- Language signed/width behavior is unclear and a readable alternative meets constraints
- The domain is not bounded enough for a mask
How it works#
Use a set/map for occurrence state or materialize every subset as separate collection state.
Write the identity or per-bit meaning in ordinary language.
Parenthesize operations and state width/signed assumptions.
Dry-run zero, highest bit, and repeated values.
InvariantEach bit has one declared meaning, and every operation preserves or toggles exactly those meanings under a stated integer width.
Example and template#
Single Number
Use XOR cancellation only after stating the input invariant.
Open the full problem brief- Pairs
a ⊕ b ⊕ aXOR is associative and commutative.
- Cancel
(a ⊕ a) ⊕ b = bEqual pairs cancel to zero; zero is the identity.
accumulator = 0
for value in input:
accumulator = accumulator XOR value
return accumulator- Time
- O(n)
- Space
- O(1)
- Assumptions
- Values use a fixed-width representation and the XOR cancellation precondition holds (all but one occur an even number of times).
Pitfalls#
Common wrong approaches
A correct expression is not interview-ready if its identity and preconditions are unstated.
Arithmetic versus logical shift and width can change results across languages.
Edge cases
- Zero
- Negative values
- Highest representable bit
- Empty input contract
Interview narration
- “Each duplicate pair cancels because x XOR x is zero.”
- “XOR order does not matter, so the unique value remains.”
- “This assumes exactly one odd-occurrence value under the stated integer representation.”
Practice#
Single Number
Use XOR cancellation only after stating the input invariant.
Practice this problemRepresent membership in a small set of feature flags and test subsets quickly.
Reveal the pattern decision
Use a bit mask because the flag universe is explicitly bounded and each bit has a stable meaning.
Transfer problem
Enumerate all subsets of n items for small n.
Checkpoint: Map mask bit i to item i and state the exponential 2^n output bound.
Follow-up variations
- Find two odd-occurrence values
- Count set bits using a clear language-supported operation
Error-log prompts
- What did each bit mean?
- Were width and signed behavior explicit?