Builds on XOR Cancel, which you haven’t finished yet.
Per-Bit Counting (Single Number II / Bitwise State Machine)
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.
2 appears three times; 3 appears once.Per-Bit Counting
value stream âž” bit registers (ones, twos, ...) âž” survivor| 1 | def single_number_ii(nums: list[int]) -> int: |
| 2 | """Modulo-3 Bitwise Finite State Machine: single element among triplets. |
| 3 | Time: O(N) | Space: O(1) |
| 4 | """ |
| 5 | ones = 0 # bits whose count so far is 1 mod 3 |
| 6 | twos = 0 # bits whose count so far is 2 mod 3 |
| 7 | Â |
| 8 | # 1. Advance Each Bit Through the 0 -> 1 -> 2 -> 0 Cycle: |
| 9 | # ones picks up a bit on its first occurrence and keeps it until a second |
| 10 | # occurrence moves it to twos; twos must be computed from the updated ones, |
| 11 | # since twos only receives a bit that ones just released. |
| 12 | for x in nums: |
| 13 | ones = (ones ^ x) & ~twos |
| 14 | twos = (twos ^ x) & ~ones |
| 15 | Â |
| 16 | return ones |
| 17 | Â |
| 18 | def single_number_ii_per_bit(nums: list[int]) -> int: |
| 19 | """Single Number II, one bit position at a time: the plain per-bit count. |
| 20 | Time: O(32 * N) | Space: O(1) |
| 21 | """ |
| 22 | res = 0 # the single value, rebuilt one bit at a time |
| 23 | Â |
| 24 | # 1. Count Each Bit Position Across Every Number: |
| 25 | # A value that appears three times adds a multiple of 3 to each of its |
| 26 | # bit's counts, so the count modulo 3 is exactly the single value's bit. |
| 27 | for bit in range(32): |
| 28 | count = sum((x >> bit) & 1 for x in nums) # How many numbers have this bit set |
| 29 | if count % 3: |
| 30 | res |= 1 << bit |
| 31 | Â |
| 32 | # 2. Fix the Sign: |
| 33 | # res is built from 32 bits as an unsigned value; Python ints have no |
| 34 | # fixed width, so a set bit 31 must be converted back to a negative number by hand. |
| 35 | if res >= 2**31: |
| 36 | res -= 2**32 |
| 37 | return res |
ones when its count so far is 1 modulo 3, in twos when it is 2, and in neither when it is 0.Count each bit position on its own: at every position, the copies of a value that appears three times add a multiple of 3, so the count modulo 3 is exactly the single value's bit. ones and twos keep that count for all positions at once: a bit is set in ones when its count so far is 1 modulo 3 and in twos when it is 2, and ones = (ones ^ x) & ~twos followed by twos = (twos ^ x) & ~ones moves each bit of x one step through 0 → 1 → 2 → 0. The trap is the order: twos must be computed from the new ones, so swapping the two lines breaks the count.
See it run
Per-Bit Counting with ones and twos, step by step
x -ones 00twos 00
Each column is one bit position. A bit set in ones means a count of 1; a bit set in twos means a count of 2.
xthe bits of the number being addedreadthe register this line readswritethe register this line writesanswerthe bits returned by the function
Start: ones = 00 and twos = 00. Every bit position has a count of 0.
Gotcha 1 of 3
- The trap
Gotcha 1: Updating
twosbeforeonesMistaketwos = (twos ^ x) & ~ones ones = (ones ^ x) & ~twosFixones = (ones ^ x) & ~twos twos = (twos ^ x) & ~onesWhat happens:
twosmust be computed from the newones. The first copy of a bit moves it intoones, and~onesthen keeps it out oftwos. With the lines swapped,twosreads the oldones. The first copy then lands intwos, and the count 0 → 1 → 2 → 0 is broken.Example: nums = [2, 2, 3, 2]Mistake: returns 0Fix: returns 3
- Every other value appears exactly twice, as in Single Number (LC 136), so an even count is all there is to cancel. See XOR Cancel
Deep Dive
Why the count modulo 3 is the single value's bit
Look at one bit position, for example bit 1. Every value that appears three times has the same bit there in all three copies. So it adds 0 or 3 to the count of that position. The single value adds 0 or 1.
The total count at one position is therefore 3k plus the single value's bit. The remainder of the count divided by 3 is exactly that bit.
Example: in [2, 2, 3, 2], bit 1 is set in all four numbers, so its count is 4. The remainder 4 % 3 is 1, and the single value 3 has bit 1 set. Bit 0 is set only in 3, so its count is 1, and the remainder is 1. Bit 2 has count 0. The result is binary 11, which is 3.
This is the idea of single_number_ii_per_bit: the 32 positions never interact, so each one is solved on its own.
The state machine in ones and twos
The per-bit loop reads the whole array 32 times. ones and twos do the same work in one pass. Together they store, for every position, a count from 0 to 2 in two bits: (twos, ones) is (0, 0) for count 0, (0, 1) for count 1, and (1, 0) for count 2.
When a position receives a 1 in x, the count must move 0 to 1, then 1 to 2, then 2 back to 0. The line ones = (ones ^ x) & ~twos flips the ones bit and keeps it off when twos is set. The line twos = (twos ^ x) & ~ones does the same for twos, using the new ones.
Trace for [2, 2, 3, 2] after each number, in binary: after the first 2, ones = 10, twos = 0. After the second 2, ones = 0, twos = 10. After 3, ones = 1, twos = 0. After the last 2, ones = 11, twos = 0. The function returns ones, which is 3.
A position whose count is a multiple of 3 ends at (0, 0). Only the single value's bits remain in ones.
Why the order of the two lines matters
In the first line, ~twos is the old twos. In the second line, ~ones must be the new ones. This order is what makes the three states a cycle.
Take a position whose count is 0 and receives a 1. The first line sets ones. The second line sees ~ones as off for this position, so twos stays off. The state is (0, 1), which is count 1.
If you write the twos line first, it reads the old ones, which is still off. It sets twos, and then the ones line is blocked by ~twos. The first copy lands in twos and the cycle breaks. With [2, 2, 3, 2] the swapped code returns 0 instead of 3.
Cost, the sign, and other counts
single_number_ii makes one pass and uses two integers: O(N) time and O(1) space. single_number_ii_per_bit makes 32 passes: O(32 * N) time and O(1) space. Both are linear in N.
Python integers have no fixed width. The ones/twos version works for negative numbers as written, because the bit operations follow the same rules on every position. The per-bit version builds res from 32 positions, so it must subtract 2**32 when res >= 2**31. For [-2, -2, -2, -4] the function then returns -4 and not 4294967292.
For a different repeat count k, the per-bit idea stays the same: test count % k. Only the shortcut changes, because ones and twos store counts up to 2 and a larger k needs more count bits. Use the per-bit loop when k is not 3.
The same per-bit view solves Total Hamming Distance (LC 477). For each position, ones_count numbers have a 1 and n - ones_count have a 0, so the position adds ones_count * (n - ones_count) to the answer. For [4, 14, 2] the total is 6.
60-Second Pitch
"XOR cancels pairs, but here every other value appears three times, so I need a different counter. I look at one bit position at a time. Triplets add a multiple of 3 to each position, so the count modulo 3 is exactly the single value's bit. The simple version loops over 32 positions, counts the 1 bits with sum((x >> bit) & 1 for x in nums), and sets the bit when count % 3 is not 0. It takes O(32 * N) time and O(1) space. I fix the sign at the end. To finish in one pass, I keep the count of every position in two integers, ones and twos, and update them in this order: ones first, then twos from the new ones. The time is O(N) and the space is O(1)."
Common Questions
- Why does XOR not solve Single Number II (LC 137)?
XOR cancels a value only when it appears an even number of times. A value that appears three times leaves one copy in the result. So the answer of XOR is mixed with every triplet. A counter modulo 3 per bit position removes the triplets completely.
- What are
onesandtwosstoring? For each bit position, they store the count of 1s seen so far, modulo 3. A position set in
oneshas count 1. A position set intwoshas count 2. A position set in neither has count 0. The two integers hold all 32 counters in parallel.- How would you change the code if every other value appeared 5 times?
Use the per-bit loop and test
count % 5. It needs no change except the modulus. The two-integer shortcut needs more registers, because counts go up to 4 and need 3 bits per position. For an interview, the per-bit loop is the safer answer.- What are the time and space complexity?
single_number_iiisO(N)time andO(1)space.single_number_ii_per_bitis O(32 * N) time andO(1)space. Because 32 is a constant, both are linear in N.- How does the same idea solve Total Hamming Distance (LC 477)?
Count per position again. If
cof thennumbers have a 1 at a position, thenc * (n - c)pairs differ there. Add this over the 32 positions. That is O(32 * N) time instead of comparing all O(N^2) pairs.
SWE Reasoning
Spot it
- Every value appears k times, with k of 3 or more, except one value that appears a different number of times. XOR alone cannot cancel an odd count, so Single Number (LC 136) logic fails.
- The question asks about the number of values that have a 1 in a given bit position, or a total over all pairs of numbers (Total Hamming Distance (LC 477)).
- The constraints ask for
O(1)extra space, which rules out a hash map of counts. - The numbers are 32-bit integers, so there are only 32 positions to examine.
The invariant, step by step
- Treat each of the 32 bit positions as its own counter. A position never affects another position.
- Copies of a repeated value add 0 or 3 to a position, so the count modulo 3 at each position equals the single value's bit.
onesandtwosstore that count modulo 3 for all positions at once: a position is inonesfor count 1, intwosfor count 2, and in neither for count 0.- For each
x,ones = (ones ^ x) & ~twosmoves a position from count 0 to 1 and from 1 to 2 out ofones. Thentwos = (twos ^ x) & ~onesmoves it from 1 to 2 and from 2 to 0 out oftwos. - After all numbers, every position that belongs to a triplet is back at count 0. Only the single value's positions are in
ones. single_number_iireturnsones.
Traps
- Lines in the wrong order. If
twosis computed beforeones, it reads the oldones. The first copy lands intwos.[2, 2, 3, 2]returns 0 instead of 3. - Testing
count == 1. The single value's bit leaves a count of3k + 1, so a count of 4 is missed. Usecount % 3. - No sign fix in the per-bit version.
resis built as an unsigned 32-bit value.[-2, -2, -2, -4]returns 4294967292 instead of -4 until you subtract2**32whenres >= 2**31. - Using XOR alone. XOR cancels pairs. Three copies leave one copy, so the result is the XOR of the single value and one copy of every other value.
- Assuming k = 3 in the shortcut. The two-register shortcut is written for counts modulo 3. For another k, use the per-bit loop with
count % k.
Practice
Builds on XOR Cancel, which you haven’t finished yet.
Per-Bit Counting (Single Number II / Bitwise State Machine)
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.
2 appears three times; 3 appears once.Per-Bit Counting
value stream âž” bit registers (ones, twos, ...) âž” survivor| 1 | def single_number_ii(nums: list[int]) -> int: |
| 2 | """Modulo-3 Bitwise Finite State Machine: single element among triplets. |
| 3 | Time: O(N) | Space: O(1) |
| 4 | """ |
| 5 | ones = 0 # bits whose count so far is 1 mod 3 |
| 6 | twos = 0 # bits whose count so far is 2 mod 3 |
| 7 | Â |
| 8 | # 1. Advance Each Bit Through the 0 -> 1 -> 2 -> 0 Cycle: |
| 9 | # ones picks up a bit on its first occurrence and keeps it until a second |
| 10 | # occurrence moves it to twos; twos must be computed from the updated ones, |
| 11 | # since twos only receives a bit that ones just released. |
| 12 | for x in nums: |
| 13 | ones = (ones ^ x) & ~twos |
| 14 | twos = (twos ^ x) & ~ones |
| 15 | Â |
| 16 | return ones |
| 17 | Â |
| 18 | def single_number_ii_per_bit(nums: list[int]) -> int: |
| 19 | """Single Number II, one bit position at a time: the plain per-bit count. |
| 20 | Time: O(32 * N) | Space: O(1) |
| 21 | """ |
| 22 | res = 0 # the single value, rebuilt one bit at a time |
| 23 | Â |
| 24 | # 1. Count Each Bit Position Across Every Number: |
| 25 | # A value that appears three times adds a multiple of 3 to each of its |
| 26 | # bit's counts, so the count modulo 3 is exactly the single value's bit. |
| 27 | for bit in range(32): |
| 28 | count = sum((x >> bit) & 1 for x in nums) # How many numbers have this bit set |
| 29 | if count % 3: |
| 30 | res |= 1 << bit |
| 31 | Â |
| 32 | # 2. Fix the Sign: |
| 33 | # res is built from 32 bits as an unsigned value; Python ints have no |
| 34 | # fixed width, so a set bit 31 must be converted back to a negative number by hand. |
| 35 | if res >= 2**31: |
| 36 | res -= 2**32 |
| 37 | return res |
ones when its count so far is 1 modulo 3, in twos when it is 2, and in neither when it is 0.Count each bit position on its own: at every position, the copies of a value that appears three times add a multiple of 3, so the count modulo 3 is exactly the single value's bit. ones and twos keep that count for all positions at once: a bit is set in ones when its count so far is 1 modulo 3 and in twos when it is 2, and ones = (ones ^ x) & ~twos followed by twos = (twos ^ x) & ~ones moves each bit of x one step through 0 → 1 → 2 → 0. The trap is the order: twos must be computed from the new ones, so swapping the two lines breaks the count.
See it run
Per-Bit Counting with ones and twos, step by step
x -ones 00twos 00
Each column is one bit position. A bit set in ones means a count of 1; a bit set in twos means a count of 2.
xthe bits of the number being addedreadthe register this line readswritethe register this line writesanswerthe bits returned by the function
Start: ones = 00 and twos = 00. Every bit position has a count of 0.
Gotcha 1 of 3
- The trap
Gotcha 1: Updating
twosbeforeonesMistaketwos = (twos ^ x) & ~ones ones = (ones ^ x) & ~twosFixones = (ones ^ x) & ~twos twos = (twos ^ x) & ~onesWhat happens:
twosmust be computed from the newones. The first copy of a bit moves it intoones, and~onesthen keeps it out oftwos. With the lines swapped,twosreads the oldones. The first copy then lands intwos, and the count 0 → 1 → 2 → 0 is broken.Example: nums = [2, 2, 3, 2]Mistake: returns 0Fix: returns 3
- Every other value appears exactly twice, as in Single Number (LC 136), so an even count is all there is to cancel. See XOR Cancel
Deep Dive
Why the count modulo 3 is the single value's bit
Look at one bit position, for example bit 1. Every value that appears three times has the same bit there in all three copies. So it adds 0 or 3 to the count of that position. The single value adds 0 or 1.
The total count at one position is therefore 3k plus the single value's bit. The remainder of the count divided by 3 is exactly that bit.
Example: in [2, 2, 3, 2], bit 1 is set in all four numbers, so its count is 4. The remainder 4 % 3 is 1, and the single value 3 has bit 1 set. Bit 0 is set only in 3, so its count is 1, and the remainder is 1. Bit 2 has count 0. The result is binary 11, which is 3.
This is the idea of single_number_ii_per_bit: the 32 positions never interact, so each one is solved on its own.
The state machine in ones and twos
The per-bit loop reads the whole array 32 times. ones and twos do the same work in one pass. Together they store, for every position, a count from 0 to 2 in two bits: (twos, ones) is (0, 0) for count 0, (0, 1) for count 1, and (1, 0) for count 2.
When a position receives a 1 in x, the count must move 0 to 1, then 1 to 2, then 2 back to 0. The line ones = (ones ^ x) & ~twos flips the ones bit and keeps it off when twos is set. The line twos = (twos ^ x) & ~ones does the same for twos, using the new ones.
Trace for [2, 2, 3, 2] after each number, in binary: after the first 2, ones = 10, twos = 0. After the second 2, ones = 0, twos = 10. After 3, ones = 1, twos = 0. After the last 2, ones = 11, twos = 0. The function returns ones, which is 3.
A position whose count is a multiple of 3 ends at (0, 0). Only the single value's bits remain in ones.
Why the order of the two lines matters
In the first line, ~twos is the old twos. In the second line, ~ones must be the new ones. This order is what makes the three states a cycle.
Take a position whose count is 0 and receives a 1. The first line sets ones. The second line sees ~ones as off for this position, so twos stays off. The state is (0, 1), which is count 1.
If you write the twos line first, it reads the old ones, which is still off. It sets twos, and then the ones line is blocked by ~twos. The first copy lands in twos and the cycle breaks. With [2, 2, 3, 2] the swapped code returns 0 instead of 3.
Cost, the sign, and other counts
single_number_ii makes one pass and uses two integers: O(N) time and O(1) space. single_number_ii_per_bit makes 32 passes: O(32 * N) time and O(1) space. Both are linear in N.
Python integers have no fixed width. The ones/twos version works for negative numbers as written, because the bit operations follow the same rules on every position. The per-bit version builds res from 32 positions, so it must subtract 2**32 when res >= 2**31. For [-2, -2, -2, -4] the function then returns -4 and not 4294967292.
For a different repeat count k, the per-bit idea stays the same: test count % k. Only the shortcut changes, because ones and twos store counts up to 2 and a larger k needs more count bits. Use the per-bit loop when k is not 3.
The same per-bit view solves Total Hamming Distance (LC 477). For each position, ones_count numbers have a 1 and n - ones_count have a 0, so the position adds ones_count * (n - ones_count) to the answer. For [4, 14, 2] the total is 6.
60-Second Pitch
"XOR cancels pairs, but here every other value appears three times, so I need a different counter. I look at one bit position at a time. Triplets add a multiple of 3 to each position, so the count modulo 3 is exactly the single value's bit. The simple version loops over 32 positions, counts the 1 bits with sum((x >> bit) & 1 for x in nums), and sets the bit when count % 3 is not 0. It takes O(32 * N) time and O(1) space. I fix the sign at the end. To finish in one pass, I keep the count of every position in two integers, ones and twos, and update them in this order: ones first, then twos from the new ones. The time is O(N) and the space is O(1)."
Common Questions
- Why does XOR not solve Single Number II (LC 137)?
XOR cancels a value only when it appears an even number of times. A value that appears three times leaves one copy in the result. So the answer of XOR is mixed with every triplet. A counter modulo 3 per bit position removes the triplets completely.
- What are
onesandtwosstoring? For each bit position, they store the count of 1s seen so far, modulo 3. A position set in
oneshas count 1. A position set intwoshas count 2. A position set in neither has count 0. The two integers hold all 32 counters in parallel.- How would you change the code if every other value appeared 5 times?
Use the per-bit loop and test
count % 5. It needs no change except the modulus. The two-integer shortcut needs more registers, because counts go up to 4 and need 3 bits per position. For an interview, the per-bit loop is the safer answer.- What are the time and space complexity?
single_number_iiisO(N)time andO(1)space.single_number_ii_per_bitis O(32 * N) time andO(1)space. Because 32 is a constant, both are linear in N.- How does the same idea solve Total Hamming Distance (LC 477)?
Count per position again. If
cof thennumbers have a 1 at a position, thenc * (n - c)pairs differ there. Add this over the 32 positions. That is O(32 * N) time instead of comparing all O(N^2) pairs.
SWE Reasoning
Spot it
- Every value appears k times, with k of 3 or more, except one value that appears a different number of times. XOR alone cannot cancel an odd count, so Single Number (LC 136) logic fails.
- The question asks about the number of values that have a 1 in a given bit position, or a total over all pairs of numbers (Total Hamming Distance (LC 477)).
- The constraints ask for
O(1)extra space, which rules out a hash map of counts. - The numbers are 32-bit integers, so there are only 32 positions to examine.
The invariant, step by step
- Treat each of the 32 bit positions as its own counter. A position never affects another position.
- Copies of a repeated value add 0 or 3 to a position, so the count modulo 3 at each position equals the single value's bit.
onesandtwosstore that count modulo 3 for all positions at once: a position is inonesfor count 1, intwosfor count 2, and in neither for count 0.- For each
x,ones = (ones ^ x) & ~twosmoves a position from count 0 to 1 and from 1 to 2 out ofones. Thentwos = (twos ^ x) & ~onesmoves it from 1 to 2 and from 2 to 0 out oftwos. - After all numbers, every position that belongs to a triplet is back at count 0. Only the single value's positions are in
ones. single_number_iireturnsones.
Traps
- Lines in the wrong order. If
twosis computed beforeones, it reads the oldones. The first copy lands intwos.[2, 2, 3, 2]returns 0 instead of 3. - Testing
count == 1. The single value's bit leaves a count of3k + 1, so a count of 4 is missed. Usecount % 3. - No sign fix in the per-bit version.
resis built as an unsigned 32-bit value.[-2, -2, -2, -4]returns 4294967292 instead of -4 until you subtract2**32whenres >= 2**31. - Using XOR alone. XOR cancels pairs. Three copies leave one copy, so the result is the XOR of the single value and one copy of every other value.
- Assuming k = 3 in the shortcut. The two-register shortcut is written for counts modulo 3. For another k, use the per-bit loop with
count % k.