Single Number II — DSA · Engineering Playbook

Single Number II

Every value appears three times except one — count bits mod 3 using two state bits (ones, twos).

Medium

Time O(n) Space O(1)

LeetCode

May 16, 2026 2 min read

Problem#

Every element appears three times except one which appears once. Find the singleton in linear time and constant space.

Examples#

[2,2,3,2] → 3.
[0,1,0,1,0,1,99] → 99.

Constraints#

1 <= nums.length <= 3 * 10^4, -2^31 <= nums[i] <= 2^31 - 1.

Approach#

Use two integers ones and twos as state machines tracking, bit-position-wise, the count mod 3 (0/1/2). Update with the canonical bitwise trick: ones = (ones ^ x) & ~twos; twos = (twos ^ x) & ~ones.

Solution#

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

func singleNumber(nums []int) int {
    ones, twos := 0, 0
    for _, x := range nums {
        ones = (ones ^ x) &^ twos
        twos = (twos ^ x) &^ ones
    }
    return ones
}

from typing import List

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ones, twos = 0, 0
        for x in nums:
            ones = (ones ^ x) & ~twos
            twos = (twos ^ x) & ~ones
        # Python ints are unbounded; sign-extend from 32 bits.
        if ones >= (1 << 31):
            ones -= 1 << 32
        return ones

function singleNumber(nums) {
    let ones = 0, twos = 0;
    for (const x of nums) {
        ones = (ones ^ x) & ~twos;
        twos = (twos ^ x) & ~ones;
    }
    return ones;
}

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;
    }
}

function singleNumber(nums: number[]): number {
    let ones = 0, twos = 0;
    for (const x of nums) {
        ones = (ones ^ x) & ~twos;
        twos = (twos ^ x) & ~ones;
    }
    return ones;
}

Editorial#

Each bit position has its own little mod-3 counter encoded by (twos_bit, ones_bit): 00 → 01 → 10 → 00. The two updates implement that transition bit-parallel across 32 bits. After processing, bits set in ones are exactly the singleton’s bits (count mod 3 = 1).

Complexity#

Time: O(n).
Space: O(1).

Concept revision#

Single Number

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#