Counting Bits
Problem
Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.
- 0 ≤ n ≤ 10⁵
Example
n = 5[0,1,1,2,1,2]The algorithm initializes an array dp of length 6 with zeros. It uses an offset variable to track the most recent power of two. For i=1, offset=1, dp[1] = 1 + dp[0] = 1. For i=2, offset updates to 2 (since 2 == 2*1), dp[2] = 1 + dp[0] = 1. For i=3, dp[3] = 1 + dp[1] = 2. For i=4, offset updates to 4, dp[4] = 1 + dp[0] = 1. For i=5, dp[5] = 1 + dp[1] = 2. This approach efficiently builds the count of set bits for each number by referencing previously computed results.
Approach
Straightforward Solution
A naive approach counts the set bits for each number individually by checking each bit, resulting in O(n log n) time complexity, which is inefficient for large n.
Core Observation
The number of set bits in a number can be derived from the number of set bits in a smaller number plus one, specifically by subtracting the largest power of two less than or equal to the number.
Path to Optimal
Recognizing that numbers between powers of two share a pattern allows the use of dynamic programming. By tracking the largest power of two (offset) less than or equal to the current number, the count of set bits for the current number can be computed as 1 plus the count for the number minus this offset. This reduces the problem to O(n) time.
Optimal Approach
Initialize a dp array of size n+1 with zeros and an offset variable set to 1. Iterate from 1 to n, updating offset when i reaches twice its value. For each i, dp[i] = 1 + dp[i - offset]. This builds the solution incrementally using previously computed results, achieving O(n) time and space complexity.
Time
O(n)
Each number from 1 to n is processed once, and each dp lookup is O(1), resulting in linear time complexity.
Space
O(n)
The dp array stores the count of set bits for all numbers from 0 to n, requiring O(n) auxiliary space.
Pattern Spotlight
Dynamic Programming (Bit Manipulation)
When counting set bits for a range of numbers, exploit the relationship between a number and the largest power of two less than or equal to it to build results incrementally, avoiding repeated bit counting.
Solution
| 1 | class Solution:
|
| 2 | def countBits(self, n: int) -> list[int]:
|
| 3 | dp = [0] * (n + 1)
|
| 4 | offset = 1
|
| 5 | for i in range(1, n + 1):
|
| 6 | if offset * 2 == i:
|
| 7 | offset = i
|
| 8 | dp[i] = 1 + dp[i - offset]
|
| 9 | return dp |
Step-by-Step Solution
Initialize DP Array and Offset Tracker
| 3 | dp = [0] * (n + 1)
|
| 4 | offset = 1
|
Objective
To prepare storage for the count of set bits for all numbers up to n and track the current largest power of two.
Key Insight
Initializing the dp array with zeros provides a base case for zero, which has zero set bits. The offset variable starts at 1, representing the smallest power of two, and will be updated dynamically as the iteration progresses to reflect the current range segment.
Interview Quick-Check
Core Logic
The dp array stores precomputed counts of set bits, enabling O(1) retrieval for subproblems.
State & Boundaries
Offset starts at 1 because 1 is the smallest power of two and serves as the initial reference point.
Iterate Through Numbers and Update Offset
| 5 | for i in range(1, n + 1):
|
| 6 | if offset * 2 == i:
|
| 7 | offset = i
|
Objective
To traverse each number from 1 to n, updating the offset when a new power of two is reached.
Key Insight
The offset update condition detects when the iteration reaches a new power of two, which resets the base for counting set bits in the current segment. This dynamic adjustment ensures that dp[i] can be computed relative to the correct offset, maintaining the correctness of the incremental counting.
Interview Quick-Check
Core Logic
Updating offset when i equals offset * 2 ensures the offset always points to the largest power of two less than or equal to i.
Common Pitfalls & Bugs
Failing to update offset at the correct time leads to incorrect dp calculations and wrong set bit counts.
Compute Set Bits Count Using DP Relation
| 8 | dp[i] = 1 + dp[i - offset]
|
Objective
To calculate the number of set bits for the current number based on the offset and previously computed results.
Key Insight
Each number i can be expressed as offset plus a remainder (i - offset). The count of set bits in i is therefore 1 (for the offset bit) plus the count of set bits in the remainder. This relation allows building the dp array incrementally without recomputing bits from scratch.
Interview Quick-Check
Core Logic
The dp relation dp[i] = 1 + dp[i - offset] exploits the binary structure of numbers to compute set bits efficiently.
Complexity
This relation enables O(n) time complexity by avoiding repeated bit counting for each number.
Return the Completed DP Array
| 9 | return dp |
Objective
To output the array containing the count of set bits for all numbers from 0 to n.
Key Insight
After filling dp with counts for all numbers, returning it provides the required result in O(1) time, as all computations are pre-done.
Interview Quick-Check
Core Logic
Returning dp directly provides the final answer without additional computation.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
dp[i] = 1 + dp[i - offset]Compute dp[i] as 1 plus dp[i - offset], counting the set bits for i.
This line embodies the core dynamic programming relation: the number of set bits in i equals one (for the highest power of two bit) plus the number of set bits in the remainder (i - offset), enabling O(1) computation per number and O(n) overall.
if offset * 2 == i:Check if i has reached the next power of two by comparing with offset * 2.
Updating offset precisely when i equals offset * 2 ensures that the dp relation uses the correct base for counting set bits, preserving correctness and enabling the incremental computation.
dp = [0] * (n + 1)Initialize a list dp of length n+1 with zeros to store set bit counts.
This array serves as the memoization table for dynamic programming, enabling constant-time access to previously computed results and establishing the base case dp[0] = 0.
offset = iUpdate offset to the current index i when a new power of two is reached.
Setting offset to i resets the base for the current segment of numbers, allowing dp[i] and subsequent values to be computed relative to this new power of two.
offset = 1Initialize offset to 1, representing the current largest power of two.
Offset tracks the most recent power of two less than or equal to the current index, which is essential for the dp relation to correctly compute set bits incrementally.
for i in range(1, n + 1):Start a loop from 1 to n inclusive to compute set bits for each number.
Iterating through all numbers ensures that dp is filled sequentially, allowing each dp[i] to rely on previously computed values for correctness and efficiency.
return dpReturn the dp array containing set bit counts for all numbers from 0 to n.
Returning dp provides the final result after all computations, completing the algorithm efficiently without further processing.
Test Your Understanding
Why does updating the offset when i equals offset * 2 correctly identify the largest power of two less than or equal to i?
Because powers of two occur at positions where i equals twice the current offset, updating offset at these points ensures it always holds the largest power of two less than or equal to i, which is essential for the dp relation.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct Counting Bits from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Counting Bits drill