Counting Bits
Understanding the Problem
We need to build an array where each index i holds the popcount (population count) of i, which is the number of 1-bits in its binary form. For example, 5 in binary is 101, so it has two 1-bits.
The brute force counts the bits of each number independently. The follow-up asks for O(n), which means reusing earlier results: the bit count of i can be derived in O(1) from the bit count of a smaller number already stored in the array. That dependency structure makes this a dynamic programming problem.
Key Constraints:
0 <= n <= 10^5→ With n up to 100,000, O(n log n) is fast enough, but the follow-up explicitly asks for O(n), so we should aim for a single-pass DP approach.- The output array itself is O(n) space, so any solution needs at least that much memory. The question is whether we need extra space beyond the output.
- The problem asks us to avoid built-in popcount functions, pushing us to implement the bit counting ourselves.
Approach 1: Brute Force (Count Bits Individually)
Intuition
For each number from 0 to n, count its 1-bits directly: check the last bit with & 1, add it to a counter, and right-shift until the number reaches 0. A number i has about log2(i) bits, so counting one number takes O(log i) work.
Built-in functions like Integer.bitCount() or __builtin_popcount compute the same value (using bit-parallel arithmetic instead of a loop), but the follow-up rules them out, so we write the loop ourselves.
Algorithm
- Create a result array of size
n + 1 - For each number
ifrom 0 ton: - Initialize a counter to 0
- While the number is greater than 0, add its last bit (
num & 1) to the counter and right-shift the number - Store the counter in
ans[i] - Return the result array
Example Walkthrough
Code
- Time Complexity: O(n log n). For each of the n + 1 numbers, we process up to log2(i) bits. The total work across all numbers sums to O(n log n).
- Space Complexity: O(1) extra space. The output array is required by the problem. Beyond that, we only use a few variables.
The waste here is that consecutive results overlap: the binary representation of i is the binary representation of i >> 1 followed by one extra bit, so counting i from scratch repeats work the array already holds. The next approach turns that overlap into an O(1) step per number.
Approach 2: DP with Right Shift
Intuition
Right-shifting a number by 1 drops its last bit and leaves every other bit unchanged. Take 13 (1101 in binary): 13 >> 1 is 6 (110). So the bit count of 13 equals the bit count of 6 plus the dropped bit, which was 1.
In general: popcount(i) = popcount(i >> 1) + (i & 1).
Since i >> 1 is always less than i, by the time we compute ans[i], the value ans[i >> 1] is already in the array. The recurrence gives each answer in O(1) time.
Algorithm
- Create a result array of size
n + 1, withans[0] = 0 - For each number
ifrom 1 ton, setans[i] = ans[i >> 1] + (i & 1). The indexi >> 1is smaller thani, so that entry is already filled - Return the result array
Example Walkthrough
Code
- Time Complexity: O(n). We iterate once from 1 to n, doing O(1) work per number (one array lookup, one shift, one AND, one addition).
- Space Complexity: O(1) extra space. The output array is required. Beyond that, no extra space is used.
O(n) is optimal, since the output itself has n + 1 entries. There is one more standard recurrence for this problem. Instead of relating i to i >> 1, it relates i to the number obtained by clearing its lowest set bit.
Approach 3: DP with Lowest Set Bit (Brian Kernighan)
Intuition
The expression i & (i - 1) clears the lowest set bit of i. For example:
6 & 5 = 110 & 101 = 100 = 4(cleared the lowest 1-bit at position 1)12 & 11 = 1100 & 1011 = 1000 = 8(cleared the lowest 1-bit at position 2)
So i & (i - 1) has exactly one fewer 1-bit than i and is always smaller than i, which gives the recurrence ans[i] = ans[i & (i - 1)] + 1.
This is the identity behind Brian Kernighan's per-number bit-counting loop, used here as a DP recurrence. The cost per entry matches Approach 2: one lookup and one addition.
Why does i & (i - 1) clear the lowest set bit? Subtracting 1 from i turns the lowest set bit into 0 and every bit below it into 1, while all higher bits stay the same. ANDing the result with i zeroes that lowest set bit (1 AND 0) and keeps the higher bits; the bits below it were already 0 in i. The result is i with exactly one 1-bit removed, and since it is strictly smaller than i, ans[i & (i - 1)] is filled before the loop reaches i.
Algorithm
- Create a result array of size
n + 1, withans[0] = 0 - For each number
ifrom 1 ton, setans[i] = ans[i & (i - 1)] + 1. The lookup hits an index smaller thani, so it is already filled, and the+ 1accounts for the cleared bit - Return the result array
Example Walkthrough
Code
- Time Complexity: O(n). One pass from 1 to n, with O(1) work per number (one AND, one subtraction, one array lookup, one addition).
- Space Complexity: O(1) extra space. Only the output array is used. No additional data structures needed.