Counting Bits (LeetCode 338)
Given an integer n, build the array ans of length n + 1 where each ans[i] (for 0 <= i <= n) holds the number of 1-bits in the binary form of i.
Worked Examples
n = 2[0,1,1]n = 5[0,1,1,2,1,2]⚖️Formal Constraints & Bounds
0 <= n <= 105
Core Insight
Right shifting i >> 1 removes the least significant bit. Therefore, the number of set bits in i is ans[i >> 1] + (i & 1). Tabulating from 1 to n achieves strict O(N) linear time.
Real-World Scenario & Production Applications
Hamming distance calculation tables, high-speed population count index precomputation in search engines, cryptographic weight generation.
Step-by-Step Execution Trace Table
Number i | Binary Representation | Right Shift i >> 1 | Lowest Bit i & 1 | Recurrence: ans[i >> 1] + (i & 1) | Result ans[i] |
|---|---|---|---|---|---|
| 0 | 0_2 | 0 | 0 | Base case | 0 |
| 1 | 1_2 | 0 | 1 | ans[0] + 1 = 0 + 1 | 1 |
| 2 | 10_2 | 1 | 0 | ans[1] + 0 = 1 + 0 | 1 |
| 3 | 11_2 | 1 | 1 | ans[1] + 1 = 1 + 1 | 2 |
| 4 | 100_2 | 2 | 0 | ans[2] + 0 = 1 + 0 | 1 |
| 5 | 101_2 | 2 | 1 | ans[2] + 1 = 1 + 1 | 2 |
The Math, Step by Step
1. The number stored for each
ans[i] must be the number of 1 bits in the binary form of , its popcount. The code fills ans from up to , and it computes each entry from an entry it has already filled.
2. Splitting into its last bit and the rest
Every whole number splits into its bits without the last one, and its last bit:
In code, the rest is i >> 1, which shifts the bits right by one place and drops the last bit. The last bit is i & 1, which keeps only bit 0. For , which is 101 in binary, i >> 1 is 10, which is 2, and i & 1 is 1.
| Last bit of | i & 1 | 1 bits of compared with i >> 1 |
|---|---|---|
| 0 ( is even) | 0 | the same |
| 1 ( is odd) | 1 | one more |
3. Why the recurrence is right, and why the order works
The 1 bits of are the 1 bits of i >> 1 plus its last bit. So
This is a dynamic programming recurrence: each answer is built from the answer to a smaller input. For , i >> 1 is smaller than . The loop goes from upward, so ans[i >> 1] is always filled before it is read.
4. The start value
ans[0] is 0, because 0 has no 1 bits. The code sets it with ans = [0] * (n + 1), and the loop starts at . For , the rule reads ans[0]: . For , the loop does not run, and the code returns [0].
5. Example 2 by hand
n = 5.
| in binary | i >> 1 | i & 1 | ans[i] = ans[i >> 1] + (i & 1) | |
|---|---|---|---|---|
| 0 | 0 | 0 (start value) | ||
| 1 | 1 | 0 | 1 | |
| 2 | 10 | 1 | 0 | |
| 3 | 11 | 1 | 1 | |
| 4 | 100 | 2 | 0 | |
| 5 | 101 | 2 | 1 |
The result [0,1,1,2,1,2] is the expected output. For example, 4 is 100 and 2 is 10: dropping the last 0 of 4 gives 2, and both have one 1 bit.
6. Example 1 by hand
n = 2. The table above gives and . The code returns [0,1,1], the expected output.
7. From the math to the code
| Math | In countBits |
|---|---|
ans = [0] * (n + 1) | |
| fill in increasing order | for i in range(1, n + 1): |
| the rest of , | i >> 1 |
| the last bit, | i & 1 |
ans[i] = ans[i >> 1] + (i & 1) |
Each entry takes one shift, one & and one addition. So the code takes time, and the output list takes space.
| 1 | ans = [0] * (n + 1) |
| 2 | for i in range(1, n + 1): |
| 3 | ans[i] = ans[i >> 1] + (i & 1) |
| 4 | return ans |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
dp[i >> 1] reaching backward into an array you're still building looks strange until you notice that every integer's binary form is literally built out of a smaller integer's binary form, plus one extra digit.
📋 The Analogy: Reusing the Answer for a Shorter Number
i >> 1 is i with its last binary digit chopped off — in other words, it's exactly the room number you get by dropping the ones-digit. Chopping off a trailing digit never changes how many 1s are in the rest of the number, so whatever answer you already computed for that shorter number is still valid; you just need to add back the one digit you chopped off, which is either 0 or 1.
You never recompute a bit count from scratch. Every number reuses the answer already stored for the number half its size.
🔑 The Key Idea in the Code
- Trick 1 (
dp[i >> 1]): The set-bit count of everything except the last binary digit — already sitting in the array becausei >> 1 < i, so it was computed on an earlier loop iteration. - Trick 2 (
i & 1): The one digit that the shift removed, added back with one AND.
Calling popcount on every number in : Computing popcount independently for each number takes . Using dynamic programming
dp[i] = dp[i >> 1] + (i & 1)computes all bit counts in strict time.Off-by-one allocating array of size instead of : The result array must hold bit counts from 0 through inclusive, requiring length .
Operator precedence omitting parentheses: In
dp[i >> 1] + (i & 1), omitting parentheses aroundi & 1results in(dp[i >> 1] + i) & 1because+has higher precedence than&.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Counting set bits for all integers in range [0, n], linear O(N) time requirement without O(N log N) per-number bit loops.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: Any integer i has the exact same number of set bits as i >> 1 (integer division by 2), plus 1 if i is odd (i & 1).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Running Kernighan's trick or
bin(i).count('1')in a loop: Takes O(N · 32) =O(N log N)time, missing the linear dynamic programming recurrence.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I allocate a
dparray of sizen + 1initialized to 0. Forifrom 1 ton, I computedp[i] = dp[i >> 1] + (i & 1). Sincei >> 1 < i, the subproblemdp[i >> 1]is already memoized. This computes bit counts for all numbers in a single pass inO(N)time andO(1)auxiliary space (excluding output).
Complexity & Mathematical Proof
O(N)
Look at the execution steps: dp[i] = dp[i >> 1] + (i & 1). Number of set bits in i equals set bits in i // 2 plus last bit. Single pass filling array from 0 to N.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Output array excluded from auxiliary space per problem spec. Uses O(1) auxiliary registers.
T(N) = N · O(1) = O(N)
Derivation Progression
dp[i] = dp[i >> 1] + (i \& 1)
Shifting right removes LSB; remaining bits already computed at index i >> 1.
O(1) bitwise shift and AND per index
Zero loops or bit iterations.
N+1 elements = O(N)
Computes all bit counts in strict linear time.
Variable Definitions
Upper integer limit (computing bit counts for integers 0 to N)
Memory Architecture & Bounds
O(1) Iterative
O(1) Zero heap memory (output array excluded)
O(N) Result array of size N + 1
Boundary Best / Worst Cases
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
The problem asks for an array ans of n + 1 entries, where ans[i] counts the 1-bits in i written in binary. Evaluating popcount(i) for every number independently would cost or . The phrase "for every number from 0 to n" is a classic structural trigger for Dynamic Programming over Bit Transitions. Specifically, right-shifting an integer i >> 1 removes its least significant bit, whose popcount was already computed!
. An linear pass where each answer is computed in time is required. The output array has length , initialized with dp[0] = 0.
Counting Bits (LeetCode 338)
Given an integer n, build the array ans of length n + 1 where each ans[i] (for 0 <= i <= n) holds the number of 1-bits in the binary form of i.
Worked Examples
n = 2[0,1,1]n = 5[0,1,1,2,1,2]⚖️Formal Constraints & Bounds
0 <= n <= 105
Core Insight
Right shifting i >> 1 removes the least significant bit. Therefore, the number of set bits in i is ans[i >> 1] + (i & 1). Tabulating from 1 to n achieves strict O(N) linear time.
Real-World Scenario & Production Applications
Hamming distance calculation tables, high-speed population count index precomputation in search engines, cryptographic weight generation.
Step-by-Step Execution Trace Table
Number i | Binary Representation | Right Shift i >> 1 | Lowest Bit i & 1 | Recurrence: ans[i >> 1] + (i & 1) | Result ans[i] |
|---|---|---|---|---|---|
| 0 | 0_2 | 0 | 0 | Base case | 0 |
| 1 | 1_2 | 0 | 1 | ans[0] + 1 = 0 + 1 | 1 |
| 2 | 10_2 | 1 | 0 | ans[1] + 0 = 1 + 0 | 1 |
| 3 | 11_2 | 1 | 1 | ans[1] + 1 = 1 + 1 | 2 |
| 4 | 100_2 | 2 | 0 | ans[2] + 0 = 1 + 0 | 1 |
| 5 | 101_2 | 2 | 1 | ans[2] + 1 = 1 + 1 | 2 |
The Math, Step by Step
1. The number stored for each
ans[i] must be the number of 1 bits in the binary form of , its popcount. The code fills ans from up to , and it computes each entry from an entry it has already filled.
2. Splitting into its last bit and the rest
Every whole number splits into its bits without the last one, and its last bit:
In code, the rest is i >> 1, which shifts the bits right by one place and drops the last bit. The last bit is i & 1, which keeps only bit 0. For , which is 101 in binary, i >> 1 is 10, which is 2, and i & 1 is 1.
| Last bit of | i & 1 | 1 bits of compared with i >> 1 |
|---|---|---|
| 0 ( is even) | 0 | the same |
| 1 ( is odd) | 1 | one more |
3. Why the recurrence is right, and why the order works
The 1 bits of are the 1 bits of i >> 1 plus its last bit. So
This is a dynamic programming recurrence: each answer is built from the answer to a smaller input. For , i >> 1 is smaller than . The loop goes from upward, so ans[i >> 1] is always filled before it is read.
4. The start value
ans[0] is 0, because 0 has no 1 bits. The code sets it with ans = [0] * (n + 1), and the loop starts at . For , the rule reads ans[0]: . For , the loop does not run, and the code returns [0].
5. Example 2 by hand
n = 5.
| in binary | i >> 1 | i & 1 | ans[i] = ans[i >> 1] + (i & 1) | |
|---|---|---|---|---|
| 0 | 0 | 0 (start value) | ||
| 1 | 1 | 0 | 1 | |
| 2 | 10 | 1 | 0 | |
| 3 | 11 | 1 | 1 | |
| 4 | 100 | 2 | 0 | |
| 5 | 101 | 2 | 1 |
The result [0,1,1,2,1,2] is the expected output. For example, 4 is 100 and 2 is 10: dropping the last 0 of 4 gives 2, and both have one 1 bit.
6. Example 1 by hand
n = 2. The table above gives and . The code returns [0,1,1], the expected output.
7. From the math to the code
| Math | In countBits |
|---|---|
ans = [0] * (n + 1) | |
| fill in increasing order | for i in range(1, n + 1): |
| the rest of , | i >> 1 |
| the last bit, | i & 1 |
ans[i] = ans[i >> 1] + (i & 1) |
Each entry takes one shift, one & and one addition. So the code takes time, and the output list takes space.
| 1 | ans = [0] * (n + 1) |
| 2 | for i in range(1, n + 1): |
| 3 | ans[i] = ans[i >> 1] + (i & 1) |
| 4 | return ans |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
dp[i >> 1] reaching backward into an array you're still building looks strange until you notice that every integer's binary form is literally built out of a smaller integer's binary form, plus one extra digit.
📋 The Analogy: Reusing the Answer for a Shorter Number
i >> 1 is i with its last binary digit chopped off — in other words, it's exactly the room number you get by dropping the ones-digit. Chopping off a trailing digit never changes how many 1s are in the rest of the number, so whatever answer you already computed for that shorter number is still valid; you just need to add back the one digit you chopped off, which is either 0 or 1.
You never recompute a bit count from scratch. Every number reuses the answer already stored for the number half its size.
🔑 The Key Idea in the Code
- Trick 1 (
dp[i >> 1]): The set-bit count of everything except the last binary digit — already sitting in the array becausei >> 1 < i, so it was computed on an earlier loop iteration. - Trick 2 (
i & 1): The one digit that the shift removed, added back with one AND.
Calling popcount on every number in : Computing popcount independently for each number takes . Using dynamic programming
dp[i] = dp[i >> 1] + (i & 1)computes all bit counts in strict time.Off-by-one allocating array of size instead of : The result array must hold bit counts from 0 through inclusive, requiring length .
Operator precedence omitting parentheses: In
dp[i >> 1] + (i & 1), omitting parentheses aroundi & 1results in(dp[i >> 1] + i) & 1because+has higher precedence than&.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Counting set bits for all integers in range [0, n], linear O(N) time requirement without O(N log N) per-number bit loops.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: Any integer i has the exact same number of set bits as i >> 1 (integer division by 2), plus 1 if i is odd (i & 1).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Running Kernighan's trick or
bin(i).count('1')in a loop: Takes O(N · 32) =O(N log N)time, missing the linear dynamic programming recurrence.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I allocate a
dparray of sizen + 1initialized to 0. Forifrom 1 ton, I computedp[i] = dp[i >> 1] + (i & 1). Sincei >> 1 < i, the subproblemdp[i >> 1]is already memoized. This computes bit counts for all numbers in a single pass inO(N)time andO(1)auxiliary space (excluding output).
Complexity & Mathematical Proof
O(N)
Look at the execution steps: dp[i] = dp[i >> 1] + (i & 1). Number of set bits in i equals set bits in i // 2 plus last bit. Single pass filling array from 0 to N.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Output array excluded from auxiliary space per problem spec. Uses O(1) auxiliary registers.
T(N) = N · O(1) = O(N)
Derivation Progression
dp[i] = dp[i >> 1] + (i \& 1)
Shifting right removes LSB; remaining bits already computed at index i >> 1.
O(1) bitwise shift and AND per index
Zero loops or bit iterations.
N+1 elements = O(N)
Computes all bit counts in strict linear time.
Variable Definitions
Upper integer limit (computing bit counts for integers 0 to N)
Memory Architecture & Bounds
O(1) Iterative
O(1) Zero heap memory (output array excluded)
O(N) Result array of size N + 1
Boundary Best / Worst Cases
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
The problem asks for an array ans of n + 1 entries, where ans[i] counts the 1-bits in i written in binary. Evaluating popcount(i) for every number independently would cost or . The phrase "for every number from 0 to n" is a classic structural trigger for Dynamic Programming over Bit Transitions. Specifically, right-shifting an integer i >> 1 removes its least significant bit, whose popcount was already computed!
. An linear pass where each answer is computed in time is required. The output array has length , initialized with dp[0] = 0.