Problem 34.6 · Bit ManipulationMedium

Single Number II

What it teaches: Count each bit position modulo 3.

Practise it on judges as “Single Number II”.

The problem

Every element appears three times except one, which appears once. Find it with O(1) extra space.

Example 1

Input: nums = [0,1,0,1,0,1,99]
Output: 99

Constraints

1 ≤ n ≤ 3 × 10⁴

Pattern clues in the wording

→ Triples cancel, not pairs

These clues point to Bit Manipulation: Use XOR, AND, OR and shifts to test, set and cancel bits, often in O(1) space.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int singleNumber(int[] nums) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	nums = [2,2,3,2]	3
2	nums = [0,1,0,1,0,1,99]	99

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Per-bit counting · O(32 n)2. Two-register state machine · O(n)

Per-bit counting

Time O(32 n) Space O(1)

For bit i, sum ((x >> i) & 1) over all x; if the sum mod 3 is 1, set bit i in the answer.

Approach 1

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int x : nums) count += (x >> i) & 1;
            if (count % 3 != 0) result |= 1 << i;
        }
        return result;
    }
}

Verdict: Generalises to "appears k times".

Two-register state machine

Time O(n) Space O(1)

ones and twos hold bits seen once and twice (mod 3): ones = (ones ^ x) & ~twos; twos = (twos ^ x) & ~ones.

Approach 2

class Solution {
    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0;
        for (int x : nums) {
            ones = (ones ^ x) & ~twos;
            twos = (twos ^ x) & ~ones;
        }
        return ones;
    }
}

Verdict: One pass; harder to derive.

Before you submit

Edge cases and common mistakes

Test these inputs

Negative single (bit 31 set)
Single element

Mistakes people make

Forgetting bit 31 (the answer can be negative).

Interview

Follow-up questions

Why does the two-register version work?

Command Palette