← DSA Atlas
Dedicated problem page · #137

Single Number II

MediumBit ManipulationBitwise finite-state counting (mod-3 per bit)Two-variable bit automaton tracking bit counts modulo 3
Solve on LeetCode ↗
137
MediumBit ManipulationTwo-variable bit automaton tracking bit counts modulo 3Bitwise finite-state counting (mod-3 per bit)

Single Number II

Given an integer array nums where every element appears exactly three times except for one element that appears exactly once, return the single element. Solve it in linear time and constant extra space.

Open official problem prompt ↗
In plain English

Find the one value appearing a single time while every other value appears three times, without extra memory.

Picture it like this

A three-state turnstile per bit: each time a bit passes, the counter advances 00 -> 01 -> 10 and snaps back to 00 on the third pass, so only bits seen a non-multiple-of-three number of times stay lit.

Example
Input
nums = [0, 1, 0, 1, 0, 1, 99]
Output
99
Why
0 and 1 each appear three times and cancel under mod-3 bit counting; 99 is the lone value.
Constraints
1 <= nums.length <= 3 * 10^4-2^31 <= nums[i] <= 2^31 - 1Each element appears exactly three times except one which appears onceMust run in O(n) time and O(1) extra space
Pattern lesson

See the pattern, then code

Bitwise finite-state counting (mod-3 per bit)
Recognition clue

Elements repeat three times (not two), so plain XOR no longer cancels. Needing O(1) space with triples signals per-bit counting modulo 3.

↗
Bit Manipulation

XOR cancellation, powers of two, compact subset state, or per-bit counting.. For each bit position, summing that bit across all numbers gives a multiple of 3 plus the single number's bit. Taking the count modulo 3 isolates the single number's bit. Two accumulators, ones and twos, act as a two-bit counter per position that resets every third occurrence.

New words, made simpleKnow these before the algorithm
Bitmask
An integer used so each bit position independently tracks state for the corresponding bit of the inputs.
Mod-3 counter
A counter that resets to zero after every third increment, matching the triple repetition.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Hash map of counts

Simple but uses linear extra space.

Count each value, return the one with count 1.

Time O(n)Space O(n)
Per-bit sum modulo 3

Correct and easy to reason about, but iterates all bits explicitly.

For each of 32 bits, sum across all numbers and take mod 3 to rebuild the answer.

Time O(32n)Space O(1)
Best choiceones/twos bit automaton

Optimal single-pass solution; the canonical answer.

Maintain two masks that together count each bit modulo 3 in a single pass.

Time O(n)Space O(1)
The rule we keep true

Invariant

After each element, for every bit position the pair (twos-bit, ones-bit) encodes how many times that bit has been seen so far, modulo 3: 00 for 0, 01 for 1, 10 for 2.

Why this is correct

Reasoning

The two update lines implement a modulo-3 increment on every bit simultaneously. A bit that has appeared a multiple of three times returns to state 00, so after processing all triples only the single number's bits remain in ones. Because the logic is purely bitwise, it works for negative numbers under two's complement as well.

The algorithm in three movesSay these aloud before coding
1Keep two masks ones and twos, both starting at 0

After three identical x: ones=0, twos=0 (reset)

2For each number x, update ones = (ones ^ x) & ~twos

A bit set once -> stored in ones

3Then update twos = (twos ^ x) & ~ones

A bit set twice -> moves to twos, cleared from ones

4After the pass, ones holds the number that appeared once

5Return ones

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
b20
b11
b02
ones3
twos4
1 · Read0
2 · Askupdate masks
3 · Update stateones=0, twos=0
4 · Resultno bits set
Key takeaway

ones/twos form a per-bit counter that cycles 00 -> 01 -> 10 -> 00 every three sightings.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3Two accumulators

    ones and twos jointly store a 2-bit mod-3 count for every bit position.

  2. 2
    Lines 5Increment into ones

    Toggle bits into ones, but mask out any bit currently held by twos so the counter advances correctly.

  3. 3
    Lines 6Increment into twos

    Symmetric step; after both lines a bit seen three times has been cleared from both masks.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Single-element array returns that element
  • Negative single number handled by two's-complement bitwise ops
  • The single value can be 0
  • Large values up to 2^31 - 1
!

Common beginner mistakes

  • Swapping the order of the ones and twos updates — the second must use the freshly updated ones
  • Assuming plain XOR works; it does not because triples do not cancel
  • In fixed-width languages, forgetting sign handling for the 32nd bit when using the per-bit-sum approach
Check your understanding

Why does the single value end up in ones rather than twos?

More in Bit Manipulation

#50Pow(x, n)Fast exponentiation (binary exponentiation)#89Gray CodeBinary-to-Gray transform (i XOR i>>1)#136Single NumberXOR cancellation#190Reverse BitsBit-by-bit reversal accumulation#191Number of 1 BitsBrian Kernighan bit clearing#201Bitwise AND of Numbers RangeCommon bit prefix