Single Number II

How it works

Two bit masks represent bits seen once and twice modulo three. Update the once mask while excluding bits already in the twice mask, then update the twice mask using the new once mask. A third occurrence clears both states, leaving the unique number in the once mask.

Steps

1. Initialize the once and twice masks to zero.
2. Update once, then twice, for every number.
3. Return the once mask.

Complexity

• Time: O(n) for fixed-width integers.
• Space: O(1).

Things to watch for

• The second update must use the newly updated once mask.
• Negative values must retain their signed bit representation.
• Ordinary XOR only cancels pairs, so it cannot handle triples.

class Solution:
  def singleNumber(self, nums: list[int]) -> int:
    ones = 0
    twos = 0

    for num in nums:
      ones ^= num & ~twos
      twos ^= num & ~ones

    return ones

class Solution {
 public:
  int singleNumber(vector<int>& nums) {
    int ones = 0;
    int twos = 0;

    for (const int num : nums) {
      ones ^= (num & ~twos);
      twos ^= (num & ~ones);
    }

    return ones;
  }
};