Why does XOR from Single Number not work here?

XOR cancels values that appear an even number of times. A value that appears three times XORs to itself (x ^ x ^ x = x), so XOR-ing everything leaves a mix of the single number and every tripled value instead of the single number alone.

Why count bits modulo 3?

Look at one bit position. Each value that appears three times adds either 0 or 3 ones there, so their total is a multiple of 3. The single value adds 0 or 1. So the count of ones modulo 3 is exactly the single value's bit in that position.

How are negative numbers handled?

In Java, C, C++ and JavaScript the result is built in a 32-bit integer, so setting bit 31 makes it negative automatically. Python integers are unbounded, so after the loop a result of 2³¹ or more is turned negative by subtracting 2³².

Is there a faster bit trick?

Yes: two masks, ones and twos, track bits seen once and twice modulo 3: ones = (ones ^ num) & ~twos; twos = (twos ^ num) & ~ones; the answer is ones. It is one pass instead of 32, still O(1) space, but harder to derive; counting per bit is the version to explain first.

Single Number II

Find the element that appears exactly once when every other element appears three times, in linear time and constant space, by counting each bit modulo 3.

MediumSolve on LeetCode

Problem Understanding

Single Number II: in nums, every element appears exactly three times except one, which appears once. Find it in linear time with constant extra space.

Examples: [2,2,3,2] → 3; [0,1,0,1,0,1,99] → 99.

The Intuition: Each Bit Is Its Own Count

Single Number cancels pairs with XOR, which is addition of bits modulo 2. Here values come in threes, so add bits modulo 3 instead:

Pick a bit position and count the numbers with a 1 there.
Triples contribute a multiple of 3, so count % 3 is 0 or 1, the single number's bit.
Repeat for all 32 positions and assemble the result.

It is the same per-bit thinking as Number of 1 Bits, applied across the whole array. A hash map count also works, at O(n) space.

Interactive Walkthrough

LOW 6 BITS SHOWN · THE REST ARE 0

result = 0

bit

count

result

count

count % 3

result

result = 0. Count the 1s in each bit position: triples add a multiple of 3, the single value adds the rest

Bit 0 (value 1): 4 numbers have a 1 here

Free preview: the first 5 of 15 steps

nums

Each number is a row of bits. The column being counted lights up its 1s, and below the grid each finished column shows its count and the result bit it produced. Try Overlap to see shared bits cancel.

Dry Run Table

Input: [2,2,3,2] (binary 10, 10, 11, 10).

Bit	1s	count % 3	result
0	1 (from 3)	1	1
1	4	1	3
2 to 31	0	0	3

Answer: 3.

The Solution Template

32 counting passes over the array. C and C++ shift as unsigned so bit 31 of a negative number is read correctly.

Single Number II Code

1var singleNumber = function(nums) {
2    let result = 0;
3    for (let bit = 0; bit < 32; bit++) {
4        let count = 0;
5        for (const num of nums) count += (num >> bit) & 1;
6        if (count % 3) result |= 1 << bit;
7    }
8    return result;
9};

Edge Cases & Common Mistakes

Negative numbers: handle bit 31 (see the sign fix); Python needs it explicitly.
Using XOR alone: triples do not cancel.
Signed shifts in C/C++: shift an unsigned copy, or right-shifting a negative value is implementation-defined.
Single element: the loop returns it unchanged.
Sorting first: works in O(n log n) but breaks the linear-time requirement.

Summary

For each of the 32 bit positions, count the 1s across all numbers; a remainder of 1 modulo 3 means the single number has that bit. O(32 · n) time, O(1) space.

More practice: DSA interview questions with answers · patterns cheat sheet

Single Number

Single Number III