Single Number II – Solution & Complexity

• XOR cancels values that appear an even number of times.
• Here duplicates appear three times (odd), so XOR does not cleanly remove them.
• We need to reason bit by bit instead.

• For each of the 32 bit positions, count how many numbers have that bit set.
• Every tripled value contributes a multiple of three, so count % 3 isolates the unique number's bits.
• Rebuild the answer from the remaining bits (sign-extending the top bit for negatives).

• Track two masks: ones holds bits seen once, twos holds bits seen twice.
• A bit resets to zero once it has been seen three times.
• After processing every number, ones is exactly the unique value.

• ones = (ones ^ num) & ~twos records bits appearing a first time while clearing any at two.
• twos = (twos ^ num) & ~ones promotes bits to the two state, clearing any now back at one.
• This is O(n) time and O(1) space with no per-bit loop.

Trace nums = [2, 2, 3, 2] (binary 2 = 10, 3 = 11).

Final ones = 01 = 3, the unique value.

The two-mask automaton returns the unique value in O(n) time and O(1) extra space.