#338 - Counting Bits
Counting Bits
- Difficulty: Easy
- Topics: Dynamic Programming, Bit Manipulation
- Link: https://leetcode.com/problems/counting-bits/
Problem Description
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
.
Example 1:
Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10
Example 2:
Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
Constraints:
0 <= n <= 105
Follow up:
- It is very easy to come up with a solution with a runtime of
O(n log n)
. Can you do it in linear timeO(n)
and possibly in a single pass? - Can you do it without using any built-in function (i.e., like
__builtin_popcount
in C++)?
Solution
1. Problem Deconstruction
Technical Restatement
Given a non-negative integer n
, compute an array ans
where each element ans[i]
(for 0 ≤ i ≤ n
) represents the Hamming weight (number of 1s) in the binary representation of i
. The solution must operate in linear time and avoid built-in bit-counting functions.
Beginner-Friendly Explanation
Imagine you need to list how many times the digit “1” appears in each number from 0 to n
when written in binary. For example, 5 in binary is 101, which has two 1s. Your task is to create this list efficiently.
Mathematical Formulation
Let f(i)
denote the number of 1s in the binary expansion of integer i
. Compute the sequence:
where
Constraint Analysis
0 ≤ n ≤ 1e5
- Limitation: Solutions must handle up to 100,000 elements efficiently.
- Edge Case:
n = 0
requires a single-element output[0]
. - Implication: O(n²) algorithms are infeasible; O(n log n) is acceptable but suboptimal.
2. Intuition Scaffolding
Real-World Analogy
Imagine a row of houses numbered 0 to n
. Each house has a binary street number (e.g., 101). You need to count the number of lit lamps (1s) in each house’s number. The challenge is to do this without rechecking all lamps every time.
Gaming Analogy
In a video game, players earn points represented in binary. To unlock achievements, track how many “power nodes” (1s) each score has. Speedrunners need this computed instantly for all scores up to level n
.
Math Analogy
Each integer’s binary form can be viewed as a vector in a hypercube. Counting 1s is equivalent to computing the Manhattan distance from the origin in this space.
Common Pitfalls
- Recalculating Bit Counts: Naively converting each number to binary and counting 1s for all
i
leads to O(n log n) time. - Ignoring Overlapping Subproblems: Failing to recognize that
f(i)
relates to smaller subproblems (e.g.,f(i) = f(i/2) + (i % 2)
). - Global Min/Max Fallacy: Assuming prior knowledge of the entire sequence is needed, rather than incremental computation.
- Bitwise Operation Misuse: Incorrectly applying bit shifts or masking (e.g., not handling even/odd cases properly).
- Off-by-One Errors: Incorrectly initializing the array or loop bounds (e.g., starting at
i=0
instead ofi=1
).
3. Approach Encyclopedia
Brute Force Approach
- Pseudocode:
def countBits(n): ans = [] for i in range(n+1): count = 0 while i > 0: count += i % 2 i = i // 2 ans.append(count) return ans
- Complexity:
- Time: O(n log n) – For each
i
, the inner loop runs log₂(i) times. - Space: O(1) (excluding output array).
- Time: O(n log n) – For each
Optimal Dynamic Programming Approach
- Key Insight: The number of 1s in
i
can be derived fromi >> 1
(integer division by 2) plus the least significant bit (LSB). - Recurrence:
- Pseudocode:
def countBits(n): ans = [0] * (n + 1) for i in range(1, n + 1): ans[i] = ans[i >> 1] + (i & 1) return ans
- Complexity Proof:
- Time: O(n) – Each of the
n
iterations performs O(1) operations. - Space: O(n) – Storing the output array.
- Time: O(n) – Each of the
Visualization
i: 0 1 2 3 4 5 6 7
b: 0 1 10 11 100 101 110 111
ans:0 1 1 2 1 2 2 3
↑ ↑ ↑ ↑
Base cases and recurrence relations via bit shifts.
4. Code Deep Dive
Optimal Code
def countBits(n):
ans = [0] * (n + 1) # Initialize array with n+1 zeros
for i in range(1, n + 1):
# ans[i >> 1] retrieves count for i//2
# (i & 1) checks the LSB (0 for even, 1 for odd)
ans[i] = ans[i >> 1] + (i & 1)
return ans
Line-by-Line Explanation
ans = [0] * (n + 1)
: Initializes the result array withn+1
elements, defaulting to 0.for i in range(1, n + 1)
: Iterates from 1 ton
(0 is pre-initialized).ans[i >> 1]
: Accesses the precomputed count fori//2
using bitwise right shift.(i & 1)
: Extracts the LSB (0 if even, 1 if odd).ans[i] = ...
: Combines the two values to compute the current count.
Edge Case Handling
- n=0: Loop doesn’t execute; returns
[0]
. - Odd/Even Split: Correctly handles LSB via
(i & 1)
.
5. Complexity War Room
Hardware-Aware Analysis
- Memory: At
n=1e5
, the output array occupies ~400KB (4 bytes per int × 100,001 elements), fitting in L3 cache. - CPU: Predictable loop with sequential memory access enables efficient pipelining.
Industry Comparison Table
Approach | Time | Space | Readability | Interview Viability |
---|---|---|---|---|
Brute Force | O(n log n) | O(1) | 8/10 | ❌ Fails large N |
DP (Optimal) | O(n) | O(n) | 9/10 | ✅ Preferred |
6. Pro Mode Extras
Variants
- Two Transactions (LC 123): Track the maximum profit for two non-overlapping buy/sell pairs.
- k Transactions (LC 188): Extend to
k
transactions using dynamic programming.
Interview Cheat Sheet
- Mention First: “This solution runs in O(n) time and O(n) space, leveraging bitwise operations and dynamic programming.”
- Key Insight: “The count of 1s for
i
depends oni//2
’s count plus the parity ofi
.”