medium

Single Number II

Find the one number in an array that does not appear exactly three times.

1. Define the problem

Single Number II

Given an integer array nums where every element appears three times except for one, which appears exactly once, find that single one. Track, for every bit position, how many times that bit has been set modulo 3 across all numbers. Only the single number contributes a remainder of 1 or 2 at any position, so what survives after every triple cancels is the answer.

Constraints

  • 1 ≤ nums.length ≤ 3 × 104
  • -231 ≤ numsi ≤ 231 - 1
  • Each element appears exactly three times except for one element which appears once

Example

Inputnums = [2, 2, 3, 2]
Output3

Explanation 2 appears three times and cancels out, leaving 3.

2. Know the words first

In plain terms

ones / twos accumulators
Two running values that together track, per bit position, whether that bit has appeared 0, 1, or 2 times so far in the current group of three — a third appearance resets it back to 0.
3. Visualize the solution

Track each bit position modulo 3 with two accumulators

Track each bit position modulo 3 with two accumulators
Statusinit

ones=0, twos=0. Process nums[0]=2 (010): ones picks up bit 010. ones=010.

What happens in this step

ones = (0 ^ 2) & ~0
  0 = 00000000
  2 = 00000010
      --------
      00000010   (0 ^ 2)
 &~0 = 11111111
      --------
      00000010  =  2   -> ones

twos = (0 ^ 2) & ~2
  0 = 00000000
  2 = 00000010
      --------
      00000010   (0 ^ 2)
 &~2 = 11111101
      --------
      00000000  =  0   -> twos

Bit 1 (value 2) has never been seen before, so it settles into ones. twos has nothing left to take because ones (freshly updated) already claimed that bit — ones=2, twos=0.
Step 1 of 4

Steps to visualize

  1. Keep two accumulators, ones and twos, both starting at 0.
  2. For each number: ones picks up any bit not already in twos, then twos picks up any bit not already in the new ones.
  3. A bit seen a third time clears itself back out of both accumulators.
  4. After every number is processed, ones holds exactly the bits of the single number.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Track each bit position modulo 3 with two accumulators
Statusinit

ones=0, twos=0. Process nums[0]=2 (010): ones picks up bit 010. ones=010.

What happens in this step

ones = (0 ^ 2) & ~0
  0 = 00000000
  2 = 00000010
      --------
      00000010   (0 ^ 2)
 &~0 = 11111111
      --------
      00000010  =  2   -> ones

twos = (0 ^ 2) & ~2
  0 = 00000000
  2 = 00000010
      --------
      00000010   (0 ^ 2)
 &~2 = 11111101
      --------
      00000000  =  0   -> twos

Bit 1 (value 2) has never been seen before, so it settles into ones. twos has nothing left to take because ones (freshly updated) already claimed that bit — ones=2, twos=0.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function singleNumber(nums) {
  let ones = 0;
  let twos = 0;

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

  return ones;
}
Time
O(n)
Space
O(1)
6. Test cases

Test cases

InputExpectedCovers
nums = [2, 2, 3, 2]3example from the docstring
nums = [0, 1, 0, 1, 0, 1, 99]99a larger single value against a triple of small numbers
nums = [5]5smallest valid input, no triples at all
nums = [-2, -2, -2, 1, 1, 1, -5]-5negative values processed alongside a negative single number
nums = [30, 30, 30, 45]45the single number appears after the triple
nums = [1, 1, 1, 2, 2, 2, 7, 7, 7, 8]8several complete triples before the single value

Keep reading