338. Counting Bits
Model: qwen3.5:9b
Topics: Dynamic Programming,Bit Manipulation
FAANG asked: 1
Acceptance rate: 70.6%
Problem Breakdown
We are given a non-negative integer num. Our goal is to construct an array where each index corresponds to the number of set bits (1s) in the binary representation of that specific integer value . The range covers all integers from 0 up to and including num inclusive.
Inputs: A single non-negative integer num.
Outputs: An integer array (list) where index holds the bit count for number , with length equal to num + 1.
Constraints & Edge Cases:
- The input is bounded by . This fits within standard memory limits.
- Negative numbers are not possible per constraints, so we don’t need to handle two’s complement edge cases for negative inputs.
- If
numis 0, the output should be[0].
Intuition
A brute-force approach would iterate from to num, and for each number, count its set bits using a helper function (like converting to binary string or shifting). This results in roughly time complexity where is the bit width (~32), which matches the follow-up warning about avoiding this.
To achieve linear time and single pass, we need an overlapping subproblem structure—Dynamic Programming (DP). The key observation lies in how binary numbers relate to each other:
- Even Numbers: If a number ends in
0(even), its bit count is identical to the number divided by two ( or ) because dividing by 2 simply removes that trailing zero, which doesn’t contribute to the set-bit count.- Example: Binary for 4 (
100) has one1. Binary for 2 (10), obtained by shifting right once, also has one1.
- Example: Binary for 4 (
- Odd Numbers: If a number ends in
1(odd), its bit count is exactly the same as plus that final1, or equivalently:- Example: Binary for 5 (
101) has two1s. Shifting right gives 2 (10). The original number had one more set bit than .
- Example: Binary for 5 (
Combining these, the recurrence relation is simply:
dp[i] = dp[i >> 1] + (i & 1)
This allows us to compute every value based on a previously computed smaller index. Since we iterate from 0 upwards, dp[i >> 1] will always be ready when needed for step .
Approach
We initialize an array of size num + 1. We set the first element (index 0) to 0 explicitly or implicitly via initialization logic since zero has no bits. Then we iterate from index 1 up to num. For each iteration, we apply our recurrence relation: take the result for half the current number and add one if the least significant bit is currently set (i & 1). This fills the array in a single pass without needing recursion or external libraries.
Complexity Analysis
- Time: . We iterate through each integer from 0 to
numexactly once, performing constant time arithmetic operations (shift and bitwise AND). - Space: for the output array required by definition of the problem. The auxiliary space is as we only use a few variables during iteration.
Solution
def countBits(num: int) -> list[int]:
# Initialize result array with zeros, size num + 1 to cover range [0, num]
dp = [0] * (num + 1)
for i in range(1, num + 1):
# Recurrence relation derived from intuition:
# Shift right by 1 removes the LSB.
# If LSB was 1 ((i & 1)), we add 1 to the count of (i >> 1).
dp[i] = dp[i >> 1] + (i & 1)
return dp
# Example usage:
print(countBits(5)) # Output: [0, 1, 1, 2, 1, 2]
Edge Cases Handled
num = 0: The looprange(1, num + 1)will not execute. We return[0], which is correct as the bit count for 0 is 0.- Large Inputs: Since we use integer arithmetic and a list of size , Python handles integers up to standard limits efficiently without overflow issues (Python ints are arbitrary precision, though here they fit in machine words).