What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

3. Triplet Bit-Counting: Single Number II (LC 137) • Invariant Proof & Speed-Run

Theory Context•Bit Manipulation

MediumLC 137

Single Number II (LeetCode 137)

Target Frequency:AmazonMicrosoftGoogle

An integer array nums has every value appearing exactly three times, except for a single value that appears only once. Return that unique value.

Your solution must run in linear time and use only constant extra space.

Worked Examples

Example 1

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

Output:3

Explanation: 2 appears three times; 3 appears once.

Example 2

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

Output:99

Explanation: 0 and 1 appear three times each; 99 appears once.

⚖️Formal Constraints & Bounds

1 <= nums.length <= 3 * 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
Each element in nums appears exactly three times except for one element which appears once.

Deep-Dive & Conceptual Insights

Core Insight

Sum the bits at each of the 32 bit positions modulo 3. Because all other elements appear three times, their bit contributions sum to multiples of 3. The remainder bit at each position forms the binary representation of the unique element.

Real-World Scenario & Production Applications

Fault detection in triple modular redundancy (TMR) systems, sensor majority-voting hardware pipelines, bit-level error isolation.

Step-by-Step Execution Trace Table

Number `x`	Binary Representation	`twos` FSM Update	`ones` FSM Update	Effective Modulo-3 Bit State
Init	—	`0000_2`	`0000_2`	All counts $0 \pmod 3$
2	`0010_2`	`0000_2`	`0010_2`	Bit 1 seen once ( $1 \pmod 3$ )
2	`0010_2`	`0010_2`	`0000_2`	Bit 1 seen twice ( $2 \pmod 3$ )
3	`0011_2`	`0000_2`	`0001_2`	Bit 0: seen once; Bit 1: seen three times (reset to $0 \pmod 3$ )
2	`0010_2`	`0000_2`	`0011_2`	Bit 0: seen once; Bit 1: seen four times ( $1 \pmod 3$ )
Final	—	`twos = 0`	`ones = 0011_2` (3)	Result is `ones = 3`

Worked on Paper

The Math, Step by Step

1. The count behind each bit

Look at one bit position $k$ at a time. Call $c_k$ the number of elements of nums that have bit $k$ set to 1.

Every value that appears three times adds either 0 or 3 to $c_k$ . The single value adds 1 if its bit $k$ is 1, and 0 if it is 0. So the remainder after dividing $c_k$ by 3 is exactly bit $k$ of the answer:

$c_k \bmod 3 = \text{bit } k \text{ of the single value}$

Here $x \bmod 3$ is the remainder after dividing $x$ by 3, so it is 0, 1 or 2.

2. Storing the remainder in two bits

The code never computes $c_k$ . It keeps $c_k \bmod 3$ while it reads nums, in two integers, ones and twos. Bit $k$ of ones and bit $k$ of twos together hold the remainder for position $k$ :

Remainder $c_k \bmod 3$	Bit $k$ of `ones`	Bit $k$ of `twos`
0	0	0
1	1	0
2	0	1

When a new element x arrives, its bit $k$ is 0 or 1. A 0 leaves the remainder unchanged. A 1 moves the remainder one step: 0 to 1, 1 to 2, and 2 back to 0. The two lines of the loop do exactly this.

Before: `ones`, `twos`	Bit $k$ of `x`	After `ones = (ones ^ x) & ~twos`	After `twos = (twos ^ x) & ~ones`	Remainder
0, 0	1	1	0	0 to 1
1, 0	1	0	1	1 to 2
0, 1	1	0	0	2 to 0
any	0	unchanged	unchanged	unchanged

In words: the first line flips the ones bit, unless the twos bit is set. & ~twos keeps a bit only where twos has a 0. The second line flips the twos bit, unless the new ones bit is set.

3. Why one pair of integers counts every bit at once

The operators ^, & and ~ act on each bit position separately. Bit $k$ of the result depends only on bit $k$ of the inputs. So the two lines run the table of part 2 in every bit position at the same time, with no loop over the bits.

After the last element, every position holds $c_k \bmod 3$ . By part 1, that remainder is 0 or 1 and equals bit $k$ of the single value. A remainder of 1 is stored in ones, and twos is 0 everywhere. So ones is the single value, and the code returns it.

4. The order of the two lines

The second line must use the new ones, the value the first line just wrote. With the old ones, the state 0, 0 would become 1, 1 after a bit of 1, which is not a remainder at all. On Example 1, that version returns 0 instead of 3.

Negative values need no special case. Python's bit operators treat a negative number as its two's complement bits, with the sign bit repeated to the left without end. Every one of those positions runs the same table, so ones ends as the negative single value itself. For example, [-2,-2,-2,-5] returns -5.

5. Example 1 by hand

nums = [2,2,3,2]. In binary, 2 is 10 and 3 is 11.

`x`	`x` in binary	`ones` after	`twos` after	Remainder in bit 1	Remainder in bit 0
2	`10`	`10`	`00`	1	0
2	`10`	`00`	`10`	2	0
3	`11`	`01`	`00`	0	1
2	`10`	`11`	`00`	1	1

Bit 1 is set in all four elements, so $c_1 = 4$ and $4 \bmod 3 = 1$ . Bit 0 is set only in the 3, so $c_0 = 1$ . Both remainders are 1, so ones ends as 11, which is 3. The code returns 3, the expected output.

6. Example 2 by hand

nums = [0,1,0,1,0,1,99]. The 0s change nothing. The three 1s move the remainder of bit 0 from 0 to 1, to 2, and back to 0. So after the first six elements, ones and twos are both 0.

`x`	`ones` after	`twos` after
0	0	0
1	1	0
0	1	0
1	0	1
0	0	1
1	0	0
99	99	0

The last element, 99, is 1100011 in binary. Each of its set bits moves a remainder from 0 to 1, so ones becomes 99. The code returns 99, the expected output.

7. From the counts to the code

Math	In `singleNumber`
every remainder starts at 0	`ones = 0` and `twos = 0`
remainder 1 in bit $k$	bit $k$ of `ones` is 1
remainder 2 in bit $k$	bit $k$ of `twos` is 1
a bit of 1 moves the remainder one step	`ones = (ones ^ x) & ~twos` then `twos = (twos ^ x) & ~ones`
$c_k \bmod 3$ is the answer's bit $k$	`return ones`

The loop does a fixed number of bit operations per element, so it takes $O(n)$ time. It keeps two integers, so it uses $O(1)$ extra space.

Code Shape

Archetype Code Shape

Python

1	ones = 0
2	twos = 0
3	for x in nums:
4	ones = (ones ^ x) & ~twos
5	twos = (twos ^ x) & ~ones
6	return ones

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

Given an integer array where every element appears three times except for one element which appears exactly once, simple XOR fails because $x \oplus x \oplus x = x$ (an odd number of occurrences does not cancel). To isolate the unique element without extra space ( $O(1)$ space), we must simulate a 3-state counter for each of the 32 bit positions simultaneously: $0 \to 1 \to 2 \to 0$ .

🏟️ The Analogy: The 3-Position Revolving Turnstile

Imagine 32 miniature revolving turnstiles side by side, each with 3 prongs marked 0, 1, and 2. Whenever an incoming number has a set bit at position $i$ , turnstile $i$ pushes forward by one notch. If a number appears 3 times, its set bits turn their corresponding turnstiles by 3 clicks, returning them exactly to 0. The solitary number clicks its turnstiles once, leaving them resting at position 1.

🔑 Why It Works

The state machine truth table per bit:

State (0, 0) + bit 1 $\to$ (1, 0) (appeared once)
State (1, 0) + bit 1 $\to$ (0, 1) (appeared twice)
State (0, 1) + bit 1 $\to$ (0, 0) (appeared three times, reset!) After iterating through all elements, all triplets reset to 0, leaving the unique single element in ones.

Python arbitrary precision negative two's complement: Python integers do not overflow at 32 bits; negative numbers have infinite sign bits. To correctly reconstruct signed 32-bit integers from bit counts, mask with 0xFFFFFFFF and convert if bit 31 is set: res if res < (1 << 31) else ~(res ^ 0xFFFFFFFF).
Modulo-3 state machine transition confusion: The two variables ones and twos track bits appearing $1 \pmod 3$ and $2 \pmod 3$ . Updating ones = (ones ^ n) & ~twos and twos = (twos ^ n) & ~ones must preserve state ordering.
Shifting more than 31 bits in 32-bit types: In C++/Java, 1 << 32 is undefined behavior. Only shift up to 31 bits.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

Pattern Recognition Signals

The 10-second spot

Array where every element appears 3 times except one unique element, O(N) time and O(1) space constraint.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Invariant: ones tracks bits seen 1 mod 3 times; twos tracks bits seen 2 mod 3 times. Bits seen 3 times reset to 0 in both registers.

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

Using standard XOR cancellation: XOR only cancels pairs (x ^ x = 0); with triples, x ^ x ^ x = x, creating false positives.
if res >= 231: res -= 232 in the per-bit version: res is built as an unsigned 32-bit value, so without it [-2, -2, -2, -4] returns 4294967292 instead of -4.
State transition order: twos must be computed from the new ones; swapping the two update lines makes [2, 2, 3, 2] return 0 instead of 3.

The 60-Second Interview Pitch

Say this out loud before you type a single line

This is Per-Bit Counting. Every number except one appears three times, so at each bit position those copies add a multiple of three, and the count modulo three is exactly the single number's bit. I keep that count for all 32 positions at once in two registers: a bit is set in ones when its count so far is one mod three, and in twos when it is two. Each number moves its bits one step through zero, one, two and back to zero. I update ones first and then twos from the new ones; swapping those two lines breaks the count. At the end ones holds the answer. That is one pass, so O(N) time, and two integers, so O(1) space.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(N)

Look at the execution steps: Tracks bit states appearing 1, 2, or 3 times using two bitmask accumulators (ones, twos). When bit appears 3 times, cleared from both. Single pass through N elements.

SPACE COMPLEXITY

O(1) Auxiliary

Look at memory allocations: Call stack uses O(1) Iterative. Two scalar integer bitmask variables (ones, twos).

Formal Recurrence Relation

T(N) = N · O(1) = O(N)

Derivation Progression

Loop Count

for x in nums → N iterations

One pass over the N numbers.

Work per Iteration

2 register updates → O(1)

Two updates on two integers, whatever the value of x.

Final Answer Extraction

return ones

ones holds unique element appearing exactly once in O(1) space.

Variable Definitions

$N$

Total number of elements in the array

Memory Architecture & Bounds

🟣 Call Stack

O(1) Iterative

🔵 Auxiliary Heap

O(1) Two 32-bit registers

🟢 Output Space

O(1) Single number integer

Boundary Best / Worst Cases

Best Case

$O(N)$

Average Case

$O(N)$

Worst Case

$O(N)$

Recurrence Tree Topology

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

The problem states: each value shows up three times, apart from one value that shows up only once. Plain XOR fails here because $x \oplus x \oplus x = x$ , meaning duplicates do not cancel to 0! To make elements appearing 3 times cancel out, each bit position must be counted modulo 3. This triggers a Bit-Level Mod-3 Finite State Machine (FSM).

CONSTRAINTS & BOUNDS

$N \le 3 \times 10^4$ , elements fit in 32-bit signed integers. Space must strictly be $O(1)$ . Counting bits with an array of size 32 takes $O(32N)$ time, but synthesizing a 2-bit counter using two 32-bit integer registers (ones and twos) processes all 32 bit-positions in parallel in a single $O(N)$ pass.

FAANG PRODUCTION TRAPS & EDGE CASES

The trap is failing to clear bits when the count transitions from 2 to 3 (which must wrap to 0). The mask ~twos ensures that if a bit was already in twos, it doesn't stay in ones. Negative numbers in Python must be handled if 32-bit two's complement sign extension occurs, though in LC 137 standard signed operations produce the correct signed integer.

Theory Context•Bit Manipulation

MediumLC 137

Single Number II (LeetCode 137)

Target Frequency:AmazonMicrosoftGoogle

An integer array nums has every value appearing exactly three times, except for a single value that appears only once. Return that unique value.

Your solution must run in linear time and use only constant extra space.

Worked Examples

Example 1

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

Output:3

Explanation: 2 appears three times; 3 appears once.

Example 2

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

Output:99

Explanation: 0 and 1 appear three times each; 99 appears once.

⚖️Formal Constraints & Bounds

1 <= nums.length <= 3 * 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
Each element in nums appears exactly three times except for one element which appears once.

Deep-Dive & Conceptual Insights

Core Insight

Real-World Scenario & Production Applications

Fault detection in triple modular redundancy (TMR) systems, sensor majority-voting hardware pipelines, bit-level error isolation.

Step-by-Step Execution Trace Table

Number `x`	Binary Representation	`twos` FSM Update	`ones` FSM Update	Effective Modulo-3 Bit State
Init	—	`0000_2`	`0000_2`	All counts $0 \pmod 3$
2	`0010_2`	`0000_2`	`0010_2`	Bit 1 seen once ( $1 \pmod 3$ )
2	`0010_2`	`0010_2`	`0000_2`	Bit 1 seen twice ( $2 \pmod 3$ )
3	`0011_2`	`0000_2`	`0001_2`	Bit 0: seen once; Bit 1: seen three times (reset to $0 \pmod 3$ )
2	`0010_2`	`0000_2`	`0011_2`	Bit 0: seen once; Bit 1: seen four times ( $1 \pmod 3$ )
Final	—	`twos = 0`	`ones = 0011_2` (3)	Result is `ones = 3`

Worked on Paper

The Math, Step by Step

1. The count behind each bit

Look at one bit position $k$ at a time. Call $c_k$ the number of elements of nums that have bit $k$ set to 1.

$c_k \bmod 3 = \text{bit } k \text{ of the single value}$

Here $x \bmod 3$ is the remainder after dividing $x$ by 3, so it is 0, 1 or 2.

2. Storing the remainder in two bits

Remainder $c_k \bmod 3$	Bit $k$ of `ones`	Bit $k$ of `twos`
0	0	0
1	1	0
2	0	1

Before: `ones`, `twos`	Bit $k$ of `x`	After `ones = (ones ^ x) & ~twos`	After `twos = (twos ^ x) & ~ones`	Remainder
0, 0	1	1	0	0 to 1
1, 0	1	0	1	1 to 2
0, 1	1	0	0	2 to 0
any	0	unchanged	unchanged	unchanged

In words: the first line flips the ones bit, unless the twos bit is set. & ~twos keeps a bit only where twos has a 0. The second line flips the twos bit, unless the new ones bit is set.

3. Why one pair of integers counts every bit at once

4. The order of the two lines

5. Example 1 by hand

nums = [2,2,3,2]. In binary, 2 is 10 and 3 is 11.

`x`	`x` in binary	`ones` after	`twos` after	Remainder in bit 1	Remainder in bit 0
2	`10`	`10`	`00`	1	0
2	`10`	`00`	`10`	2	0
3	`11`	`01`	`00`	0	1
2	`10`	`11`	`00`	1	1

6. Example 2 by hand

nums = [0,1,0,1,0,1,99]. The 0s change nothing. The three 1s move the remainder of bit 0 from 0 to 1, to 2, and back to 0. So after the first six elements, ones and twos are both 0.

`x`	`ones` after	`twos` after
0	0	0
1	1	0
0	1	0
1	0	1
0	0	1
1	0	0
99	99	0

The last element, 99, is 1100011 in binary. Each of its set bits moves a remainder from 0 to 1, so ones becomes 99. The code returns 99, the expected output.

7. From the counts to the code

Math	In `singleNumber`
every remainder starts at 0	`ones = 0` and `twos = 0`
remainder 1 in bit $k$	bit $k$ of `ones` is 1
remainder 2 in bit $k$	bit $k$ of `twos` is 1
a bit of 1 moves the remainder one step	`ones = (ones ^ x) & ~twos` then `twos = (twos ^ x) & ~ones`
$c_k \bmod 3$ is the answer's bit $k$	`return ones`

The loop does a fixed number of bit operations per element, so it takes $O(n)$ time. It keeps two integers, so it uses $O(1)$ extra space.

Code Shape

Archetype Code Shape

Python

1	ones = 0
2	twos = 0
3	for x in nums:
4	ones = (ones ^ x) & ~twos
5	twos = (twos ^ x) & ~ones
6	return ones

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

🏟️ The Analogy: The 3-Position Revolving Turnstile

🔑 Why It Works

The state machine truth table per bit:

State (0, 0) + bit 1 $\to$ (1, 0) (appeared once)
State (1, 0) + bit 1 $\to$ (0, 1) (appeared twice)
State (0, 1) + bit 1 $\to$ (0, 0) (appeared three times, reset!) After iterating through all elements, all triplets reset to 0, leaving the unique single element in ones.

Python arbitrary precision negative two's complement: Python integers do not overflow at 32 bits; negative numbers have infinite sign bits. To correctly reconstruct signed 32-bit integers from bit counts, mask with 0xFFFFFFFF and convert if bit 31 is set: res if res < (1 << 31) else ~(res ^ 0xFFFFFFFF).
Modulo-3 state machine transition confusion: The two variables ones and twos track bits appearing $1 \pmod 3$ and $2 \pmod 3$ . Updating ones = (ones ^ n) & ~twos and twos = (twos ^ n) & ~ones must preserve state ordering.
Shifting more than 31 bits in 32-bit types: In C++/Java, 1 << 32 is undefined behavior. Only shift up to 31 bits.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

Pattern Recognition Signals

The 10-second spot

Array where every element appears 3 times except one unique element, O(N) time and O(1) space constraint.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Invariant: ones tracks bits seen 1 mod 3 times; twos tracks bits seen 2 mod 3 times. Bits seen 3 times reset to 0 in both registers.

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

Using standard XOR cancellation: XOR only cancels pairs (x ^ x = 0); with triples, x ^ x ^ x = x, creating false positives.
if res >= 231: res -= 232 in the per-bit version: res is built as an unsigned 32-bit value, so without it [-2, -2, -2, -4] returns 4294967292 instead of -4.
State transition order: twos must be computed from the new ones; swapping the two update lines makes [2, 2, 3, 2] return 0 instead of 3.

The 60-Second Interview Pitch

Say this out loud before you type a single line

This is Per-Bit Counting. Every number except one appears three times, so at each bit position those copies add a multiple of three, and the count modulo three is exactly the single number's bit. I keep that count for all 32 positions at once in two registers: a bit is set in ones when its count so far is one mod three, and in twos when it is two. Each number moves its bits one step through zero, one, two and back to zero. I update ones first and then twos from the new ones; swapping those two lines breaks the count. At the end ones holds the answer. That is one pass, so O(N) time, and two integers, so O(1) space.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(N)

Look at the execution steps: Tracks bit states appearing 1, 2, or 3 times using two bitmask accumulators (ones, twos). When bit appears 3 times, cleared from both. Single pass through N elements.

SPACE COMPLEXITY

O(1) Auxiliary

Look at memory allocations: Call stack uses O(1) Iterative. Two scalar integer bitmask variables (ones, twos).

Formal Recurrence Relation

T(N) = N · O(1) = O(N)

Derivation Progression

Loop Count

for x in nums → N iterations

One pass over the N numbers.

Work per Iteration

2 register updates → O(1)

Two updates on two integers, whatever the value of x.

Final Answer Extraction

return ones

ones holds unique element appearing exactly once in O(1) space.

Variable Definitions

$N$

Total number of elements in the array

Memory Architecture & Bounds

🟣 Call Stack

O(1) Iterative

🔵 Auxiliary Heap

O(1) Two 32-bit registers

🟢 Output Space

O(1) Single number integer

Boundary Best / Worst Cases

Best Case

$O(N)$

Average Case

$O(N)$

Worst Case

$O(N)$

Recurrence Tree Topology

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

FAANG PRODUCTION TRAPS & EDGE CASES

Number x

Binary Representation

twos FSM Update

ones FSM Update

Effective Modulo-3 Bit State

Init

—

0000_2

All counts

0 \pmod 3

0010_2

0000_2

0010_2

Bit 1 seen once (

1 \pmod 3

)

0010_2

0000_2

Bit 1 seen twice (

2 \pmod 3

)

0011_2

0000_2

0001_2

Bit 0: seen once; Bit 1: seen three times (reset to

0 \pmod 3

)

0010_2

0000_2

0011_2

Bit 0: seen once; Bit 1: seen four times (

1 \pmod 3

)

Final

—

twos = 0

ones = 0011_2 (3)

Result is ones = 3

c_k \bmod 3

k

k

Before: ones, twos

k

After ones = (ones ^ x) & ~twos

After twos = (twos ^ x) & ~ones

Remainder

0, 0

0 to 1

1, 0

1 to 2

0, 1

2 to 0

any

unchanged

x

x in binary

ones after

twos after

Remainder in bit 1

Remainder in bit 0

10

00

10

00

10

11

01

00

10

11

00

x

ones after

twos after

Math

In singleNumber

every remainder starts at 0

ones = 0 and twos = 0

remainder 1 in bit

k

bit

k

of ones is 1

remainder 2 in bit

k

bit

k

of twos is 1

a bit of 1 moves the remainder one step

ones = (ones ^ x) & ~twos then twos = (twos ^ x) & ~ones

c_k \bmod 3

is the answer's bit

k

return ones

Number x

Binary Representation

twos FSM Update

ones FSM Update

Effective Modulo-3 Bit State

Init

—

0000_2

All counts

0 \pmod 3

0010_2

0000_2

0010_2

Bit 1 seen once (

1 \pmod 3

)

0010_2

0000_2

Bit 1 seen twice (

2 \pmod 3

)

0011_2

0000_2

0001_2

Bit 0: seen once; Bit 1: seen three times (reset to

0 \pmod 3

)

0010_2

0000_2

0011_2

Bit 0: seen once; Bit 1: seen four times (

1 \pmod 3

)

Final

—

twos = 0

ones = 0011_2 (3)

Result is ones = 3

c_k \bmod 3

k

k

Before: ones, twos

k

After ones = (ones ^ x) & ~twos

After twos = (twos ^ x) & ~ones

Remainder

0, 0

0 to 1

1, 0

1 to 2

0, 1

2 to 0

any

unchanged

x

x in binary

ones after

twos after

Remainder in bit 1

Remainder in bit 0

10

00

10

00

10

11

01

00

10

11

00

x

ones after

twos after

Math

In singleNumber

every remainder starts at 0

ones = 0 and twos = 0

remainder 1 in bit

k

bit

k

of ones is 1

remainder 2 in bit

k

bit

k

of twos is 1

a bit of 1 moves the remainder one step

ones = (ones ^ x) & ~twos then twos = (twos ^ x) & ~ones

c_k \bmod 3

is the answer's bit

k

return ones

🧭 Conceptual Foundation & Pattern Intuition

🏟️ The Analogy: The 3-Position Revolving Turnstile

🔑 Why It Works

The state machine truth table per bit:

State (0, 0) + bit 1 $\to$ (1, 0) (appeared once)
State (1, 0) + bit 1 $\to$ (0, 1) (appeared twice)
State (0, 1) + bit 1 $\to$ (0, 0) (appeared three times, reset!) After iterating through all elements, all triplets reset to 0, leaving the unique single element in ones.