Problem statement

Given an integer array nums where every element appears exactly three times except for one, which appears once, find that single element.

Solve it in linear time using constant extra space.

Example 1

Input: nums = [2,2,3,2]
Output: 3

Example 2

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

Example 3

Input: nums = [-2,-2,1,1,-3,1,-3,-3,-4,-2]
Output: -4

Constraints

• 1 <= nums.length <= 40
• -1000000 <= nums[i] <= 1000000
• Every element appears three times except one, which appears once.

Hints for Single Number II

1. Hint 1

   XOR alone does not work — it cancels pairs, not triples.

2. Hint 2

   Look at each of the 32 bit positions independently and count how many numbers have that bit set.

3. Hint 3

   That count is a multiple of 3 plus the loner's bit, so count % 3 recovers the answer bit by bit; sign-extend for negatives.

How to solve Single Number II

Count, for each of the 32 bit positions, how many numbers have that bit set. Every triple contributes a multiple of three, so count % 3 is the loner's bit.

Approach

1. For each bit 0..31, sum (x >> bit) & 1 over the array.
2. If the sum is not divisible by 3, set that bit in the answer.
3. Sign-extend: if bit 31 is set, subtract 2³².

Why it works

Bits are independent under counting: the tripled numbers add 0 or 3 to each position's tally, so the residue mod 3 is exactly the single number's bit.

Complexity

• Time — O(32 · n)
• Space — O(1)

Pitfalls

• Plain XOR cancels pairs, not triples.
• Forgetting the sign extension returns a large positive value for a negative loner.

Reference solution

Python

def singleNumber(nums) -> int:
    answer = 0
    for bit in range(32):
        ones = sum((x >> bit) & 1 for x in nums)
        if ones % 3:
            answer |= 1 << bit
    if answer >= (1 << 31):
        answer -= 1 << 32
    return answer

Java

public static int singleNumber(int[] nums) {
    int answer = 0;
    for (int bit = 0; bit < 32; bit++) {
        int ones = 0;
        for (int x : nums) ones += (x >> bit) & 1;
        if (ones % 3 != 0) answer |= 1 << bit;
    }
    return answer;
}

C++

int singleNumber(vector<int>& nums) {
    int answer = 0;
    for (int bit = 0; bit < 32; bit++) {
        int ones = 0;
        for (int x : nums) ones += (x >> bit) & 1;
        if (ones % 3 != 0) answer |= 1 << bit;
    }
    return answer;
}

JavaScript

var singleNumber = function(nums) {
    let answer = 0;
    for (let bit = 0; bit < 32; bit++) {
        let ones = 0;
        for (let i = 0; i < nums.length; i++) ones += (nums[i] >> bit) & 1;
        if (ones % 3 !== 0) answer |= 1 << bit;
    }
    return answer | 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium