← Back to DSA Animator
Single Number II LC #137 Medium Bit Count mod 3
Problem

Given an integer array nums where every element appears exactly three times except for one element which appears exactly once. Find the single element and return it. You must implement a solution with linear runtime and constant extra space.

Example 1
Input: nums = [2,2,3,2]
Output: 3
Explanation: 2 appears 3 times; 3 appears once.
Example 2
Input: nums = [0,1,0,1,0,1,99]
Output: 99
Explanation: 99 appears once; others 3 times.
Constraints: 1 ≤ nums.length ≤ 3·10⁴ | Each element appears exactly 3 times except for one
Try Examples
Custom:
Input Array
Bit State (ones / twos)
ones:
twos:
Variables
ones
0
twos
0
n (current)
—
Step Logic
Press ▶ Play or Next Step to begin.
✅
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
ones = bits seen exactly 1 time (mod 3)
2
twos = bits seen exactly 2 times (mod 3)
3
At 3 occurrences both ones and twos reset to 0
4
Unique number remains in ones at the end
Time
O(n)
Space
O(1)
Why It Works

Track each bit's count mod 3 with two bit-arrays: ones and twos. ones holds bits whose cumulative count mod 3 is 1; twos holds bits whose count mod 3 is 2. When a bit appears 3 times it clears from both (count mod 3 = 0). The single number's bits appear only once and never reach count 3, so they remain in ones. The update formula ones = (ones^n) & ~twos and twos = (twos^n) & ~ones implements this 3-state machine atomically for all 32 bits simultaneously.