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.

Theory Context•Bit Manipulation

P0EasyMental model~4 min speedrun

XOR Trick (Single Number / XOR Partitioning)

Grows into

Per-Bit Counting

Single Number (LC 136)(opens leetcode.com)

You're given a non-empty array of integers nums where every value shows up twice except for exactly one value that shows up only once. Return that lone value.

Your solution must run in linear time and use only constant extra space — no sorting, no hash map.

Example 1

Input:nums = [2,2,1]

Output:1

2 appears twice; 1 appears once.

XOR Cancel

stream of numbers ➔ one accumulator ➔ the unpaired answer

Spot it when: Every value appears an even number of times except one or two, or you must find what is missing or extra between two collections, using O(1) extra space.

XOR Cancel

Python

1	def single_number(nums: list[int]) -> int:
2	"""Single Number: every value appears twice except one.
3	Time: O(N) \| Space: O(1)
4	"""
5	res = 0 # running XOR of every value seen so far
6
7	# 1. Cancel Paired Values:
8	# XOR each value into res; a value that appears twice XORs with itself
9	# and vanishes, so only the value that appears once survives in res.
10	for num in nums:
11	res ^= num
12	return res
13
14	def single_number_iii(nums: list[int]) -> list[int]:
15	"""Single Number III: two values appear once, every other value twice.
16	Time: O(N) \| Space: O(1)
17	"""
18	xor_all = 0 # running XOR of every value; ends as a ^ b (the two singles)
19
20	# 1. Combine All Values:
21	# XOR every value into xor_all; every value that appears twice cancels,
22	# leaving a ^ b for the two values that each appear once.
23	for num in nums:
24	xor_all ^= num
25
26	# 2. Find a Distinguishing Bit:
27	# a and b differ in every bit that is set in xor_all; keep only the
28	# lowest such bit so the next step can split numbers into two groups by it.
29	diff_bit = xor_all & (-xor_all)
30
31	a, b = 0, 0 # accumulators for each group; each ends holding one of a, b
32
33	# 3. Split and Cancel Within Each Group:
34	# Every value with the bit set is grouped into a (duplicates among them
35	# still cancel there); every value without it is grouped into b the same way.
36	for num in nums:
37	if num & diff_bit:
38	a ^= num
39	else:
40	b ^= num
41
42	return [a, b]

Invariant: After each number, res (or xor_all, a and b) is the XOR of the numbers seen so far, so every value seen an even number of times has cancelled out.

Feed every number through res ^= num. Because x ^ x = 0 and x ^ 0 = x, and XOR does not care about order, every value that appears an even number of times cancels; the accumulator is left holding the value that appeared an odd number of times. The trap is the starting value: res = 0 is right because 0 is the one value XOR leaves unchanged; starting at res = nums[0] while the loop still visits every number XORs nums[0] in twice, so it cancels itself.

See it run

Single Number: XOR every value into res, nums = [4, 1, 2, 1, 2]

res 0 (000)

The top row is nums. The bottom row shows res after each number has been XORed in.

num the number being read
partner an earlier copy of the same value
res res after this number
answer the final res

res starts at 0, because x ^ 0 = x. Starting at nums[0] and still reading every number would XOR nums[0] twice.

nums

res

1 / 12

Gotchas1 of 4

The trap
Gotcha 1: Starting at res = nums[0] instead of res = 0
Mistake
```
res = nums[0]
```
Fix
```
res = 0
```
What happens: The loop XORs every number into res, nums[0] included. Starting at nums[0] XORs it in a second time. Two copies cancel, so nums[0] disappears from res. res = 0 is the right start, because x ^ 0 = x.
Example: nums = [4, 1, 2, 1, 2]
Mistake: returns 0Fix: returns 4
Gotcha 2: Using XOR when duplicates appear three times
Mistake
```
return single_number(nums)
```
Fix
```
return single_number_ii(nums)
```
What happens: XOR removes a value only when it appears an even number of times. In Single Number II (LC 137), each duplicate appears three times. Three copies XOR to one copy, so the duplicates stay in res. Count each bit instead, as the Per-Bit Counting card does in single_number_ii.
Example: Single Number II (LC 137): nums = [2, 2, 3, 2]
Mistake: returns 1Fix: returns 3
Gotcha 3: Using xor_all & (xor_all - 1) as the split bit
Mistake
```
diff_bit = xor_all & (xor_all - 1)
```
Fix
```
diff_bit = xor_all & (-xor_all)
```
What happens: In Single Number III (LC 260), xor_all is a ^ b, so each set bit is a place where a and b differ. xor_all & (-xor_all) keeps only the lowest set bit. xor_all & (xor_all - 1) removes that bit instead. When xor_all has one set bit, the result is 0, and every number goes to b. In C++, negating INT_MIN is undefined behavior, so compute diff_bit on an unsigned copy there.
Example: Single Number III (LC 260): nums = [1, 1, 2, 6]
Mistake: returns [0, 4]Fix: returns [6, 2]
Gotcha 4: Testing num & diff_bit == 1
Mistake
```
if num & diff_bit == 1:
```
Fix
```
if num & diff_bit:
```
What happens: num & diff_bit is either 0 or diff_bit itself. It equals 1 only when diff_bit is 1. For any other diff_bit, the test == 1 is always False, and every number goes to b.
Example: nums = [1, 2, 1, 3, 2, 5]
Mistake: returns [0, 6]Fix: returns [3, 5]

Not this one if…

Every other value appears three times instead of twice, as in Single Number II (LC 137): an odd count no longer cancels to zero. See Per-Bit Counting

Deep Dive

Why the accumulator ends on the single value

XOR (written ^) compares two numbers bit by bit. For each bit position, the result bit is 1 when exactly one of the two input bits is 1.

Three facts make the card work. x ^ x = 0, because every bit equals itself. x ^ 0 = x, because XOR with a 0 bit changes nothing. And XOR gives the same result in any order, so the numbers can be regrouped freely.

In Single Number (LC 136), res ^= num for [4, 1, 2, 1, 2] runs as 0, 4, 5, 7, 6, 4. Regroup the same values as 4 ^ (1 ^ 1) ^ (2 ^ 2). Each pair becomes 0, and 4 ^ 0 ^ 0 is 4.

This is why the card's invariant says that res is the XOR of the numbers seen so far. Every value seen an even number of times has cancelled, whatever the order of the input.

Even and odd counts: when the trick applies

XOR does not remove duplicates. It removes pairs. A value that appears an even number of times cancels completely. A value that appears an odd number of times leaves exactly one copy in res.

So single_number also works when the other values appear 2, 4 or 6 times. For [4, 1, 2, 1, 2, 4, 4], the value 4 appears three times, and the result is 4.

This is also the limit. If every other value appears three times, as in Single Number II (LC 137), each triple leaves one copy behind. The card named Per-Bit Counting handles that case.

Two singles: split them with one bit

In Single Number III (LC 260), two values a and b appear once. After the first loop, xor_all equals a ^ b, because everything else cancels. A single XOR cannot separate two values, so the card splits the input into two groups.

a and b are different, so xor_all has at least one bit set. At that bit, one of the two values has a 1 and the other has a 0. diff_bit = xor_all & (-xor_all) keeps only the lowest such bit.

Each number goes to group a when num & diff_bit is non-zero, and to group b otherwise. A pair of equal numbers has the same bit, so both copies land in the same group and cancel there. The two singles land in different groups. Each group then reduces to one single.

Example: for [1, 2, 1, 3, 2, 5], xor_all is 3 ^ 5 = 0b110, and diff_bit is 0b010. Group a holds 2, 3 and 2, which reduce to 3. Group b holds 1, 1 and 5, which reduce to 5.

The cost: one pass, no extra memory

The card's complexity line is Time O(N) and Space O(1). single_number visits each of the N numbers once and does one XOR on each. It keeps only the integer res.

single_number_iii makes two passes, which is still O(N). It keeps xor_all, diff_bit, a and b, which is O(1) space.

A hash set also solves Single Number (LC 136) in O(N) time, but it uses O(N) space. The XOR version is the answer when the problem asks for constant extra space.

60-Second Pitch

"A set or a counter solves it in O(N) space. The problem asks for O(1), so I use XOR. XOR has three properties. x ^ x is 0, x ^ 0 is x, and the order does not matter. So if I XOR every number into res, starting at 0, each pair cancels and only the single value remains. That takes one pass and one integer, so it is O(N) time and O(1) space. If two values appear once, the first pass gives a ^ b. I take the lowest set bit of that result, which is a bit where a and b differ. I XOR the numbers with that bit set into one accumulator and the others into a second one. Pairs stay together, the singles are separated, and the two accumulators end as a and b."

Common Questions

Why does the trick work, and why is the order of the numbers irrelevant?: XOR is commutative and associative, so any regrouping gives the same result. Regroup the values so that equal ones are next to each other. Each equal pair gives x ^ x = 0, and 0 changes nothing. Only the unpaired value remains.
Why start with res = 0?: Because x ^ 0 = x, so 0 is the identity value of XOR and the first res ^= num gives num exactly. Starting at nums[0] and then looping over all numbers XORs nums[0] twice, which cancels it.
What changes if every other value appears three times?: XOR no longer works, because three copies XOR to one copy. In Single Number II (LC 137), count each bit position modulo 3. The Per-Bit Counting card shows this. The single value is the number whose bits have a count of 1 modulo 3.
How do you find two single values in Single Number III (LC 260)?: XOR everything to get a ^ b. Take the lowest set bit with xor_all & (-xor_all). This is a bit where a and b differ. Split the numbers by that bit, and XOR each group. Equal numbers always fall in the same group, so every pair cancels inside its group. The two accumulators end as a and b.
How would you find a missing number with XOR?: In Missing Number (LC 268), XOR every index from 0 to N with every value in nums. Each number that is present appears twice, once as an index and once as a value, and cancels. The missing number appears once and remains. This takes O(N) time and O(1) space.

SWE Reasoning

Spot it

Every value appears an even number of times, except one or two values.
The problem asks for O(1) extra space, so a hash set or a counter is not allowed.
You must find what is missing or extra between two collections, as in Missing Number (LC 268) or Find the Difference (LC 389). Put both collections through the same XOR pass.
The wording says pairs, twice, or the same value appearing again. Pairing is the sign that XOR can cancel.
The order of the input does not matter.

The invariant, step by step

res starts at 0. This is the value that XOR leaves unchanged, so res is the XOR of zero numbers.
The loop reads num and runs res ^= num. Now res is the XOR of the numbers read so far.
When a value appears for the second time, res ^= num XORs it with its first copy, and the two copies contribute 0.
At any moment, every value seen an even number of times has contributed nothing. Every value seen an odd number of times has contributed one copy.
At the end, only the value that appears an odd number of times is left. That value is the answer.
For two singles, the same argument gives xor_all = a ^ b. The bit diff_bit splits the numbers so that each group has exactly one single, and the argument repeats inside each group.

Traps

Start at res = nums[0] and still loop over every number. nums[0] is XORed twice, so it cancels itself. For [4, 1, 2, 1, 2], the result is 0 instead of 4. Start at res = 0.
Duplicates appear three times. Three copies XOR to one copy, so the duplicates stay in res. Use the Per-Bit Counting card for Single Number II (LC 137).
Wrong split bit. xor_all & (xor_all - 1) removes the lowest set bit instead of keeping it. For [1, 1, 2, 6], xor_all is 0b100, and the wrong formula gives 0. Every number goes to b, and the result is [0, 4] instead of [6, 2]. Use xor_all & (-xor_all).
if num & diff_bit == 1. num & diff_bit is either 0 or diff_bit, so it equals 1 only when diff_bit is 1. For any other diff_bit, every number goes to b, and [1, 2, 1, 3, 2, 5] returns [0, 6] instead of [3, 5]. Use if num & diff_bit:.
Answer is not guaranteed. If the input can have no single value, or more than one, res is the XOR of all odd-count values, which may not be a value from the input. The card relies on the guarantee in the problem statement.

Practice

Canonical LeetCode:Single Number (LC 136)Find the Difference (LC 389)Single Number III (LC 260)Decode XORed Array (LC 1720)Set Mismatch (LC 645)Missing Number (LC 268)

Theory Context•Bit Manipulation

P0EasyMental model~4 min speedrun

XOR Trick (Single Number / XOR Partitioning)

Grows into

Per-Bit Counting

Single Number (LC 136)(opens leetcode.com)

You're given a non-empty array of integers nums where every value shows up twice except for exactly one value that shows up only once. Return that lone value.

Your solution must run in linear time and use only constant extra space — no sorting, no hash map.

Example 1

Input:nums = [2,2,1]

Output:1

2 appears twice; 1 appears once.

XOR Cancel

stream of numbers ➔ one accumulator ➔ the unpaired answer

Spot it when: Every value appears an even number of times except one or two, or you must find what is missing or extra between two collections, using O(1) extra space.

XOR Cancel

Python

1	def single_number(nums: list[int]) -> int:
2	"""Single Number: every value appears twice except one.
3	Time: O(N) \| Space: O(1)
4	"""
5	res = 0 # running XOR of every value seen so far
6
7	# 1. Cancel Paired Values:
8	# XOR each value into res; a value that appears twice XORs with itself
9	# and vanishes, so only the value that appears once survives in res.
10	for num in nums:
11	res ^= num
12	return res
13
14	def single_number_iii(nums: list[int]) -> list[int]:
15	"""Single Number III: two values appear once, every other value twice.
16	Time: O(N) \| Space: O(1)
17	"""
18	xor_all = 0 # running XOR of every value; ends as a ^ b (the two singles)
19
20	# 1. Combine All Values:
21	# XOR every value into xor_all; every value that appears twice cancels,
22	# leaving a ^ b for the two values that each appear once.
23	for num in nums:
24	xor_all ^= num
25
26	# 2. Find a Distinguishing Bit:
27	# a and b differ in every bit that is set in xor_all; keep only the
28	# lowest such bit so the next step can split numbers into two groups by it.
29	diff_bit = xor_all & (-xor_all)
30
31	a, b = 0, 0 # accumulators for each group; each ends holding one of a, b
32
33	# 3. Split and Cancel Within Each Group:
34	# Every value with the bit set is grouped into a (duplicates among them
35	# still cancel there); every value without it is grouped into b the same way.
36	for num in nums:
37	if num & diff_bit:
38	a ^= num
39	else:
40	b ^= num
41
42	return [a, b]

Invariant: After each number, res (or xor_all, a and b) is the XOR of the numbers seen so far, so every value seen an even number of times has cancelled out.

See it run

Single Number: XOR every value into res, nums = [4, 1, 2, 1, 2]

res 0 (000)

The top row is nums. The bottom row shows res after each number has been XORed in.

num the number being read
partner an earlier copy of the same value
res res after this number
answer the final res

res starts at 0, because x ^ 0 = x. Starting at nums[0] and still reading every number would XOR nums[0] twice.

nums

res

1 / 12

Gotchas1 of 4

The trap
Gotcha 1: Starting at res = nums[0] instead of res = 0
Mistake
```
res = nums[0]
```
Fix
```
res = 0
```
What happens: The loop XORs every number into res, nums[0] included. Starting at nums[0] XORs it in a second time. Two copies cancel, so nums[0] disappears from res. res = 0 is the right start, because x ^ 0 = x.
Example: nums = [4, 1, 2, 1, 2]
Mistake: returns 0Fix: returns 4
Gotcha 2: Using XOR when duplicates appear three times
Mistake
```
return single_number(nums)
```
Fix
```
return single_number_ii(nums)
```
What happens: XOR removes a value only when it appears an even number of times. In Single Number II (LC 137), each duplicate appears three times. Three copies XOR to one copy, so the duplicates stay in res. Count each bit instead, as the Per-Bit Counting card does in single_number_ii.
Example: Single Number II (LC 137): nums = [2, 2, 3, 2]
Mistake: returns 1Fix: returns 3
Gotcha 3: Using xor_all & (xor_all - 1) as the split bit
Mistake
```
diff_bit = xor_all & (xor_all - 1)
```
Fix
```
diff_bit = xor_all & (-xor_all)
```
What happens: In Single Number III (LC 260), xor_all is a ^ b, so each set bit is a place where a and b differ. xor_all & (-xor_all) keeps only the lowest set bit. xor_all & (xor_all - 1) removes that bit instead. When xor_all has one set bit, the result is 0, and every number goes to b. In C++, negating INT_MIN is undefined behavior, so compute diff_bit on an unsigned copy there.
Example: Single Number III (LC 260): nums = [1, 1, 2, 6]
Mistake: returns [0, 4]Fix: returns [6, 2]
Gotcha 4: Testing num & diff_bit == 1
Mistake
```
if num & diff_bit == 1:
```
Fix
```
if num & diff_bit:
```
What happens: num & diff_bit is either 0 or diff_bit itself. It equals 1 only when diff_bit is 1. For any other diff_bit, the test == 1 is always False, and every number goes to b.
Example: nums = [1, 2, 1, 3, 2, 5]
Mistake: returns [0, 6]Fix: returns [3, 5]

Not this one if…

Every other value appears three times instead of twice, as in Single Number II (LC 137): an odd count no longer cancels to zero. See Per-Bit Counting

Deep Dive

Why the accumulator ends on the single value

XOR (written ^) compares two numbers bit by bit. For each bit position, the result bit is 1 when exactly one of the two input bits is 1.

In Single Number (LC 136), res ^= num for [4, 1, 2, 1, 2] runs as 0, 4, 5, 7, 6, 4. Regroup the same values as 4 ^ (1 ^ 1) ^ (2 ^ 2). Each pair becomes 0, and 4 ^ 0 ^ 0 is 4.

This is why the card's invariant says that res is the XOR of the numbers seen so far. Every value seen an even number of times has cancelled, whatever the order of the input.

Even and odd counts: when the trick applies

XOR does not remove duplicates. It removes pairs. A value that appears an even number of times cancels completely. A value that appears an odd number of times leaves exactly one copy in res.

So single_number also works when the other values appear 2, 4 or 6 times. For [4, 1, 2, 1, 2, 4, 4], the value 4 appears three times, and the result is 4.

This is also the limit. If every other value appears three times, as in Single Number II (LC 137), each triple leaves one copy behind. The card named Per-Bit Counting handles that case.

Two singles: split them with one bit

a and b are different, so xor_all has at least one bit set. At that bit, one of the two values has a 1 and the other has a 0. diff_bit = xor_all & (-xor_all) keeps only the lowest such bit.

Example: for [1, 2, 1, 3, 2, 5], xor_all is 3 ^ 5 = 0b110, and diff_bit is 0b010. Group a holds 2, 3 and 2, which reduce to 3. Group b holds 1, 1 and 5, which reduce to 5.

The cost: one pass, no extra memory

The card's complexity line is Time O(N) and Space O(1). single_number visits each of the N numbers once and does one XOR on each. It keeps only the integer res.

single_number_iii makes two passes, which is still O(N). It keeps xor_all, diff_bit, a and b, which is O(1) space.

A hash set also solves Single Number (LC 136) in O(N) time, but it uses O(N) space. The XOR version is the answer when the problem asks for constant extra space.

60-Second Pitch

Common Questions

Why does the trick work, and why is the order of the numbers irrelevant?: XOR is commutative and associative, so any regrouping gives the same result. Regroup the values so that equal ones are next to each other. Each equal pair gives x ^ x = 0, and 0 changes nothing. Only the unpaired value remains.
Why start with res = 0?: Because x ^ 0 = x, so 0 is the identity value of XOR and the first res ^= num gives num exactly. Starting at nums[0] and then looping over all numbers XORs nums[0] twice, which cancels it.
What changes if every other value appears three times?: XOR no longer works, because three copies XOR to one copy. In Single Number II (LC 137), count each bit position modulo 3. The Per-Bit Counting card shows this. The single value is the number whose bits have a count of 1 modulo 3.
How do you find two single values in Single Number III (LC 260)?: XOR everything to get a ^ b. Take the lowest set bit with xor_all & (-xor_all). This is a bit where a and b differ. Split the numbers by that bit, and XOR each group. Equal numbers always fall in the same group, so every pair cancels inside its group. The two accumulators end as a and b.
How would you find a missing number with XOR?: In Missing Number (LC 268), XOR every index from 0 to N with every value in nums. Each number that is present appears twice, once as an index and once as a value, and cancels. The missing number appears once and remains. This takes O(N) time and O(1) space.

SWE Reasoning

Spot it

Every value appears an even number of times, except one or two values.
The problem asks for O(1) extra space, so a hash set or a counter is not allowed.
You must find what is missing or extra between two collections, as in Missing Number (LC 268) or Find the Difference (LC 389). Put both collections through the same XOR pass.
The wording says pairs, twice, or the same value appearing again. Pairing is the sign that XOR can cancel.
The order of the input does not matter.

The invariant, step by step

res starts at 0. This is the value that XOR leaves unchanged, so res is the XOR of zero numbers.
The loop reads num and runs res ^= num. Now res is the XOR of the numbers read so far.
When a value appears for the second time, res ^= num XORs it with its first copy, and the two copies contribute 0.
At any moment, every value seen an even number of times has contributed nothing. Every value seen an odd number of times has contributed one copy.
At the end, only the value that appears an odd number of times is left. That value is the answer.
For two singles, the same argument gives xor_all = a ^ b. The bit diff_bit splits the numbers so that each group has exactly one single, and the argument repeats inside each group.

Traps

Start at res = nums[0] and still loop over every number. nums[0] is XORed twice, so it cancels itself. For [4, 1, 2, 1, 2], the result is 0 instead of 4. Start at res = 0.
Duplicates appear three times. Three copies XOR to one copy, so the duplicates stay in res. Use the Per-Bit Counting card for Single Number II (LC 137).
Wrong split bit. xor_all & (xor_all - 1) removes the lowest set bit instead of keeping it. For [1, 1, 2, 6], xor_all is 0b100, and the wrong formula gives 0. Every number goes to b, and the result is [0, 4] instead of [6, 2]. Use xor_all & (-xor_all).
if num & diff_bit == 1. num & diff_bit is either 0 or diff_bit, so it equals 1 only when diff_bit is 1. For any other diff_bit, every number goes to b, and [1, 2, 1, 3, 2, 5] returns [0, 6] instead of [3, 5]. Use if num & diff_bit:.
Answer is not guaranteed. If the input can have no single value, or more than one, res is the XOR of all odd-count values, which may not be a value from the input. The card relies on the guarantee in the problem statement.

Practice

Canonical LeetCode:Single Number (LC 136)Find the Difference (LC 389)Single Number III (LC 260)Decode XORed Array (LC 1720)Set Mismatch (LC 645)Missing Number (LC 268)

Theory Context•Bit Manipulation

P0EasyMental model~4 min speedrun

XOR Trick (Single Number / XOR Partitioning)

Grows into

Per-Bit Counting

Single Number (LC 136)(opens leetcode.com)

You're given a non-empty array of integers nums where every value shows up twice except for exactly one value that shows up only once. Return that lone value.

Your solution must run in linear time and use only constant extra space — no sorting, no hash map.

Example 1

Input:nums = [2,2,1]

Output:1

2 appears twice; 1 appears once.

XOR Cancel

stream of numbers ➔ one accumulator ➔ the unpaired answer

Spot it when: Every value appears an even number of times except one or two, or you must find what is missing or extra between two collections, using O(1) extra space.

XOR Cancel

Python

1	def single_number(nums: list[int]) -> int:
2	"""Single Number: every value appears twice except one.
3	Time: O(N) \| Space: O(1)
4	"""
5	res = 0 # running XOR of every value seen so far
6
7	# 1. Cancel Paired Values:
8	# XOR each value into res; a value that appears twice XORs with itself
9	# and vanishes, so only the value that appears once survives in res.
10	for num in nums:
11	res ^= num
12	return res
13
14	def single_number_iii(nums: list[int]) -> list[int]:
15	"""Single Number III: two values appear once, every other value twice.
16	Time: O(N) \| Space: O(1)
17	"""
18	xor_all = 0 # running XOR of every value; ends as a ^ b (the two singles)
19
20	# 1. Combine All Values:
21	# XOR every value into xor_all; every value that appears twice cancels,
22	# leaving a ^ b for the two values that each appear once.
23	for num in nums:
24	xor_all ^= num
25
26	# 2. Find a Distinguishing Bit:
27	# a and b differ in every bit that is set in xor_all; keep only the
28	# lowest such bit so the next step can split numbers into two groups by it.
29	diff_bit = xor_all & (-xor_all)
30
31	a, b = 0, 0 # accumulators for each group; each ends holding one of a, b
32
33	# 3. Split and Cancel Within Each Group:
34	# Every value with the bit set is grouped into a (duplicates among them
35	# still cancel there); every value without it is grouped into b the same way.
36	for num in nums:
37	if num & diff_bit:
38	a ^= num
39	else:
40	b ^= num
41
42	return [a, b]

Invariant: After each number, res (or xor_all, a and b) is the XOR of the numbers seen so far, so every value seen an even number of times has cancelled out.

See it run

Single Number: XOR every value into res, nums = [4, 1, 2, 1, 2]

res 0 (000)

The top row is nums. The bottom row shows res after each number has been XORed in.

num the number being read
partner an earlier copy of the same value
res res after this number
answer the final res

res starts at 0, because x ^ 0 = x. Starting at nums[0] and still reading every number would XOR nums[0] twice.

nums

res

1 / 12

Gotchas1 of 4

The trap
Gotcha 1: Starting at res = nums[0] instead of res = 0
Mistake
```
res = nums[0]
```
Fix
```
res = 0
```
What happens: The loop XORs every number into res, nums[0] included. Starting at nums[0] XORs it in a second time. Two copies cancel, so nums[0] disappears from res. res = 0 is the right start, because x ^ 0 = x.
Example: nums = [4, 1, 2, 1, 2]
Mistake: returns 0Fix: returns 4
Gotcha 2: Using XOR when duplicates appear three times
Mistake
```
return single_number(nums)
```
Fix
```
return single_number_ii(nums)
```
What happens: XOR removes a value only when it appears an even number of times. In Single Number II (LC 137), each duplicate appears three times. Three copies XOR to one copy, so the duplicates stay in res. Count each bit instead, as the Per-Bit Counting card does in single_number_ii.
Example: Single Number II (LC 137): nums = [2, 2, 3, 2]
Mistake: returns 1Fix: returns 3
Gotcha 3: Using xor_all & (xor_all - 1) as the split bit
Mistake
```
diff_bit = xor_all & (xor_all - 1)
```
Fix
```
diff_bit = xor_all & (-xor_all)
```
What happens: In Single Number III (LC 260), xor_all is a ^ b, so each set bit is a place where a and b differ. xor_all & (-xor_all) keeps only the lowest set bit. xor_all & (xor_all - 1) removes that bit instead. When xor_all has one set bit, the result is 0, and every number goes to b. In C++, negating INT_MIN is undefined behavior, so compute diff_bit on an unsigned copy there.
Example: Single Number III (LC 260): nums = [1, 1, 2, 6]
Mistake: returns [0, 4]Fix: returns [6, 2]
Gotcha 4: Testing num & diff_bit == 1
Mistake
```
if num & diff_bit == 1:
```
Fix
```
if num & diff_bit:
```
What happens: num & diff_bit is either 0 or diff_bit itself. It equals 1 only when diff_bit is 1. For any other diff_bit, the test == 1 is always False, and every number goes to b.
Example: nums = [1, 2, 1, 3, 2, 5]
Mistake: returns [0, 6]Fix: returns [3, 5]

Not this one if…

Every other value appears three times instead of twice, as in Single Number II (LC 137): an odd count no longer cancels to zero. See Per-Bit Counting

Deep Dive

Why the accumulator ends on the single value

XOR (written ^) compares two numbers bit by bit. For each bit position, the result bit is 1 when exactly one of the two input bits is 1.

In Single Number (LC 136), res ^= num for [4, 1, 2, 1, 2] runs as 0, 4, 5, 7, 6, 4. Regroup the same values as 4 ^ (1 ^ 1) ^ (2 ^ 2). Each pair becomes 0, and 4 ^ 0 ^ 0 is 4.

This is why the card's invariant says that res is the XOR of the numbers seen so far. Every value seen an even number of times has cancelled, whatever the order of the input.

Even and odd counts: when the trick applies

XOR does not remove duplicates. It removes pairs. A value that appears an even number of times cancels completely. A value that appears an odd number of times leaves exactly one copy in res.

So single_number also works when the other values appear 2, 4 or 6 times. For [4, 1, 2, 1, 2, 4, 4], the value 4 appears three times, and the result is 4.

This is also the limit. If every other value appears three times, as in Single Number II (LC 137), each triple leaves one copy behind. The card named Per-Bit Counting handles that case.

Two singles: split them with one bit

a and b are different, so xor_all has at least one bit set. At that bit, one of the two values has a 1 and the other has a 0. diff_bit = xor_all & (-xor_all) keeps only the lowest such bit.

Example: for [1, 2, 1, 3, 2, 5], xor_all is 3 ^ 5 = 0b110, and diff_bit is 0b010. Group a holds 2, 3 and 2, which reduce to 3. Group b holds 1, 1 and 5, which reduce to 5.

The cost: one pass, no extra memory

The card's complexity line is Time O(N) and Space O(1). single_number visits each of the N numbers once and does one XOR on each. It keeps only the integer res.

single_number_iii makes two passes, which is still O(N). It keeps xor_all, diff_bit, a and b, which is O(1) space.

A hash set also solves Single Number (LC 136) in O(N) time, but it uses O(N) space. The XOR version is the answer when the problem asks for constant extra space.

60-Second Pitch

Common Questions

Why does the trick work, and why is the order of the numbers irrelevant?: XOR is commutative and associative, so any regrouping gives the same result. Regroup the values so that equal ones are next to each other. Each equal pair gives x ^ x = 0, and 0 changes nothing. Only the unpaired value remains.
Why start with res = 0?: Because x ^ 0 = x, so 0 is the identity value of XOR and the first res ^= num gives num exactly. Starting at nums[0] and then looping over all numbers XORs nums[0] twice, which cancels it.
What changes if every other value appears three times?: XOR no longer works, because three copies XOR to one copy. In Single Number II (LC 137), count each bit position modulo 3. The Per-Bit Counting card shows this. The single value is the number whose bits have a count of 1 modulo 3.
How do you find two single values in Single Number III (LC 260)?: XOR everything to get a ^ b. Take the lowest set bit with xor_all & (-xor_all). This is a bit where a and b differ. Split the numbers by that bit, and XOR each group. Equal numbers always fall in the same group, so every pair cancels inside its group. The two accumulators end as a and b.
How would you find a missing number with XOR?: In Missing Number (LC 268), XOR every index from 0 to N with every value in nums. Each number that is present appears twice, once as an index and once as a value, and cancels. The missing number appears once and remains. This takes O(N) time and O(1) space.

SWE Reasoning

Spot it

Every value appears an even number of times, except one or two values.
The problem asks for O(1) extra space, so a hash set or a counter is not allowed.
You must find what is missing or extra between two collections, as in Missing Number (LC 268) or Find the Difference (LC 389). Put both collections through the same XOR pass.
The wording says pairs, twice, or the same value appearing again. Pairing is the sign that XOR can cancel.
The order of the input does not matter.

The invariant, step by step

res starts at 0. This is the value that XOR leaves unchanged, so res is the XOR of zero numbers.
The loop reads num and runs res ^= num. Now res is the XOR of the numbers read so far.
When a value appears for the second time, res ^= num XORs it with its first copy, and the two copies contribute 0.
At any moment, every value seen an even number of times has contributed nothing. Every value seen an odd number of times has contributed one copy.
At the end, only the value that appears an odd number of times is left. That value is the answer.
For two singles, the same argument gives xor_all = a ^ b. The bit diff_bit splits the numbers so that each group has exactly one single, and the argument repeats inside each group.

Traps

Start at res = nums[0] and still loop over every number. nums[0] is XORed twice, so it cancels itself. For [4, 1, 2, 1, 2], the result is 0 instead of 4. Start at res = 0.
Duplicates appear three times. Three copies XOR to one copy, so the duplicates stay in res. Use the Per-Bit Counting card for Single Number II (LC 137).
Wrong split bit. xor_all & (xor_all - 1) removes the lowest set bit instead of keeping it. For [1, 1, 2, 6], xor_all is 0b100, and the wrong formula gives 0. Every number goes to b, and the result is [0, 4] instead of [6, 2]. Use xor_all & (-xor_all).
if num & diff_bit == 1. num & diff_bit is either 0 or diff_bit, so it equals 1 only when diff_bit is 1. For any other diff_bit, every number goes to b, and [1, 2, 1, 3, 2, 5] returns [0, 6] instead of [3, 5]. Use if num & diff_bit:.
Answer is not guaranteed. If the input can have no single value, or more than one, res is the XOR of all odd-count values, which may not be a value from the input. The card relies on the guarantee in the problem statement.

Practice

Canonical LeetCode:Single Number (LC 136)Find the Difference (LC 389)Single Number III (LC 260)Decode XORed Array (LC 1720)Set Mismatch (LC 645)Missing Number (LC 268)

Theory Context•Bit Manipulation

P0EasyMental model~4 min speedrun

XOR Trick (Single Number / XOR Partitioning)

Grows into

Per-Bit Counting

Single Number (LC 136)(opens leetcode.com)

You're given a non-empty array of integers nums where every value shows up twice except for exactly one value that shows up only once. Return that lone value.

Your solution must run in linear time and use only constant extra space — no sorting, no hash map.

Example 1

Input:nums = [2,2,1]

Output:1

2 appears twice; 1 appears once.

XOR Cancel

stream of numbers ➔ one accumulator ➔ the unpaired answer

Spot it when: Every value appears an even number of times except one or two, or you must find what is missing or extra between two collections, using O(1) extra space.

XOR Cancel

Python

1	def single_number(nums: list[int]) -> int:
2	"""Single Number: every value appears twice except one.
3	Time: O(N) \| Space: O(1)
4	"""
5	res = 0 # running XOR of every value seen so far
6
7	# 1. Cancel Paired Values:
8	# XOR each value into res; a value that appears twice XORs with itself
9	# and vanishes, so only the value that appears once survives in res.
10	for num in nums:
11	res ^= num
12	return res
13
14	def single_number_iii(nums: list[int]) -> list[int]:
15	"""Single Number III: two values appear once, every other value twice.
16	Time: O(N) \| Space: O(1)
17	"""
18	xor_all = 0 # running XOR of every value; ends as a ^ b (the two singles)
19
20	# 1. Combine All Values:
21	# XOR every value into xor_all; every value that appears twice cancels,
22	# leaving a ^ b for the two values that each appear once.
23	for num in nums:
24	xor_all ^= num
25
26	# 2. Find a Distinguishing Bit:
27	# a and b differ in every bit that is set in xor_all; keep only the
28	# lowest such bit so the next step can split numbers into two groups by it.
29	diff_bit = xor_all & (-xor_all)
30
31	a, b = 0, 0 # accumulators for each group; each ends holding one of a, b
32
33	# 3. Split and Cancel Within Each Group:
34	# Every value with the bit set is grouped into a (duplicates among them
35	# still cancel there); every value without it is grouped into b the same way.
36	for num in nums:
37	if num & diff_bit:
38	a ^= num
39	else:
40	b ^= num
41
42	return [a, b]

Invariant: After each number, res (or xor_all, a and b) is the XOR of the numbers seen so far, so every value seen an even number of times has cancelled out.

See it run

Single Number: XOR every value into res, nums = [4, 1, 2, 1, 2]

res 0 (000)

The top row is nums. The bottom row shows res after each number has been XORed in.

num the number being read
partner an earlier copy of the same value
res res after this number
answer the final res

res starts at 0, because x ^ 0 = x. Starting at nums[0] and still reading every number would XOR nums[0] twice.

nums

res

1 / 12

Gotchas1 of 4

The trap
Gotcha 1: Starting at res = nums[0] instead of res = 0
Mistake
```
res = nums[0]
```
Fix
```
res = 0
```
What happens: The loop XORs every number into res, nums[0] included. Starting at nums[0] XORs it in a second time. Two copies cancel, so nums[0] disappears from res. res = 0 is the right start, because x ^ 0 = x.
Example: nums = [4, 1, 2, 1, 2]
Mistake: returns 0Fix: returns 4
Gotcha 2: Using XOR when duplicates appear three times
Mistake
```
return single_number(nums)
```
Fix
```
return single_number_ii(nums)
```
What happens: XOR removes a value only when it appears an even number of times. In Single Number II (LC 137), each duplicate appears three times. Three copies XOR to one copy, so the duplicates stay in res. Count each bit instead, as the Per-Bit Counting card does in single_number_ii.
Example: Single Number II (LC 137): nums = [2, 2, 3, 2]
Mistake: returns 1Fix: returns 3
Gotcha 3: Using xor_all & (xor_all - 1) as the split bit
Mistake
```
diff_bit = xor_all & (xor_all - 1)
```
Fix
```
diff_bit = xor_all & (-xor_all)
```
What happens: In Single Number III (LC 260), xor_all is a ^ b, so each set bit is a place where a and b differ. xor_all & (-xor_all) keeps only the lowest set bit. xor_all & (xor_all - 1) removes that bit instead. When xor_all has one set bit, the result is 0, and every number goes to b. In C++, negating INT_MIN is undefined behavior, so compute diff_bit on an unsigned copy there.
Example: Single Number III (LC 260): nums = [1, 1, 2, 6]
Mistake: returns [0, 4]Fix: returns [6, 2]
Gotcha 4: Testing num & diff_bit == 1
Mistake
```
if num & diff_bit == 1:
```
Fix
```
if num & diff_bit:
```
What happens: num & diff_bit is either 0 or diff_bit itself. It equals 1 only when diff_bit is 1. For any other diff_bit, the test == 1 is always False, and every number goes to b.
Example: nums = [1, 2, 1, 3, 2, 5]
Mistake: returns [0, 6]Fix: returns [3, 5]

Not this one if…

Every other value appears three times instead of twice, as in Single Number II (LC 137): an odd count no longer cancels to zero. See Per-Bit Counting

Deep Dive

Why the accumulator ends on the single value

XOR (written ^) compares two numbers bit by bit. For each bit position, the result bit is 1 when exactly one of the two input bits is 1.

In Single Number (LC 136), res ^= num for [4, 1, 2, 1, 2] runs as 0, 4, 5, 7, 6, 4. Regroup the same values as 4 ^ (1 ^ 1) ^ (2 ^ 2). Each pair becomes 0, and 4 ^ 0 ^ 0 is 4.

This is why the card's invariant says that res is the XOR of the numbers seen so far. Every value seen an even number of times has cancelled, whatever the order of the input.

Even and odd counts: when the trick applies

XOR does not remove duplicates. It removes pairs. A value that appears an even number of times cancels completely. A value that appears an odd number of times leaves exactly one copy in res.

So single_number also works when the other values appear 2, 4 or 6 times. For [4, 1, 2, 1, 2, 4, 4], the value 4 appears three times, and the result is 4.

This is also the limit. If every other value appears three times, as in Single Number II (LC 137), each triple leaves one copy behind. The card named Per-Bit Counting handles that case.

Two singles: split them with one bit

a and b are different, so xor_all has at least one bit set. At that bit, one of the two values has a 1 and the other has a 0. diff_bit = xor_all & (-xor_all) keeps only the lowest such bit.

Example: for [1, 2, 1, 3, 2, 5], xor_all is 3 ^ 5 = 0b110, and diff_bit is 0b010. Group a holds 2, 3 and 2, which reduce to 3. Group b holds 1, 1 and 5, which reduce to 5.

The cost: one pass, no extra memory

The card's complexity line is Time O(N) and Space O(1). single_number visits each of the N numbers once and does one XOR on each. It keeps only the integer res.

single_number_iii makes two passes, which is still O(N). It keeps xor_all, diff_bit, a and b, which is O(1) space.

A hash set also solves Single Number (LC 136) in O(N) time, but it uses O(N) space. The XOR version is the answer when the problem asks for constant extra space.

60-Second Pitch

Common Questions

Why does the trick work, and why is the order of the numbers irrelevant?: XOR is commutative and associative, so any regrouping gives the same result. Regroup the values so that equal ones are next to each other. Each equal pair gives x ^ x = 0, and 0 changes nothing. Only the unpaired value remains.
Why start with res = 0?: Because x ^ 0 = x, so 0 is the identity value of XOR and the first res ^= num gives num exactly. Starting at nums[0] and then looping over all numbers XORs nums[0] twice, which cancels it.
What changes if every other value appears three times?: XOR no longer works, because three copies XOR to one copy. In Single Number II (LC 137), count each bit position modulo 3. The Per-Bit Counting card shows this. The single value is the number whose bits have a count of 1 modulo 3.
How do you find two single values in Single Number III (LC 260)?: XOR everything to get a ^ b. Take the lowest set bit with xor_all & (-xor_all). This is a bit where a and b differ. Split the numbers by that bit, and XOR each group. Equal numbers always fall in the same group, so every pair cancels inside its group. The two accumulators end as a and b.
How would you find a missing number with XOR?: In Missing Number (LC 268), XOR every index from 0 to N with every value in nums. Each number that is present appears twice, once as an index and once as a value, and cancels. The missing number appears once and remains. This takes O(N) time and O(1) space.

SWE Reasoning

Spot it

Every value appears an even number of times, except one or two values.
The problem asks for O(1) extra space, so a hash set or a counter is not allowed.
You must find what is missing or extra between two collections, as in Missing Number (LC 268) or Find the Difference (LC 389). Put both collections through the same XOR pass.
The wording says pairs, twice, or the same value appearing again. Pairing is the sign that XOR can cancel.
The order of the input does not matter.

The invariant, step by step

res starts at 0. This is the value that XOR leaves unchanged, so res is the XOR of zero numbers.
The loop reads num and runs res ^= num. Now res is the XOR of the numbers read so far.
When a value appears for the second time, res ^= num XORs it with its first copy, and the two copies contribute 0.
At any moment, every value seen an even number of times has contributed nothing. Every value seen an odd number of times has contributed one copy.
At the end, only the value that appears an odd number of times is left. That value is the answer.
For two singles, the same argument gives xor_all = a ^ b. The bit diff_bit splits the numbers so that each group has exactly one single, and the argument repeats inside each group.

Traps

Start at res = nums[0] and still loop over every number. nums[0] is XORed twice, so it cancels itself. For [4, 1, 2, 1, 2], the result is 0 instead of 4. Start at res = 0.
Duplicates appear three times. Three copies XOR to one copy, so the duplicates stay in res. Use the Per-Bit Counting card for Single Number II (LC 137).
Wrong split bit. xor_all & (xor_all - 1) removes the lowest set bit instead of keeping it. For [1, 1, 2, 6], xor_all is 0b100, and the wrong formula gives 0. Every number goes to b, and the result is [0, 4] instead of [6, 2]. Use xor_all & (-xor_all).
if num & diff_bit == 1. num & diff_bit is either 0 or diff_bit, so it equals 1 only when diff_bit is 1. For any other diff_bit, every number goes to b, and [1, 2, 1, 3, 2, 5] returns [0, 6] instead of [3, 5]. Use if num & diff_bit:.
Answer is not guaranteed. If the input can have no single value, or more than one, res is the XOR of all odd-count values, which may not be a value from the input. The card relies on the guarantee in the problem statement.

Practice

Canonical LeetCode:Single Number (LC 136)Find the Difference (LC 389)Single Number III (LC 260)Decode XORed Array (LC 1720)Set Mismatch (LC 645)Missing Number (LC 268)