Domain 2MediumCORE

Counting Bits

We are given a non-negative integer num. Our goal is to construct an array where each index $i$ corresponds to the number of set bits (1s) in the binary representation of that specific integer value $i$. The range covers all integers from 0 up to and including num inclusive.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Dynamic Programming#Bit Manipulation

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 ii corresponds to the number of set bits (1s) in the binary representation of that specific integer value ii. 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 kk holds the bit count for number kk, with length equal to num + 1. Constraints & Edge Cases:

  • The input is bounded by 0≤num≤1050 \le num \le 10^5. 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 num is 0, the output should be [0].

Intuition

A brute-force approach would iterate from 00 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 O(N⋅K)O(N \cdot K) time complexity where KK is the bit width (~32), which matches the follow-up warning about avoiding this.

To achieve linear time O(n)O(n) and single pass, we need an overlapping subproblem structure—Dynamic Programming (DP). The key observation lies in how binary numbers relate to each other:

  1. Even Numbers: If a number ends in 0 (even), its bit count is identical to the number divided by two (i/2i/2 or i>>1i >> 1) because dividing by 2 simply removes that trailing zero, which doesn’t contribute to the set-bit count.
    • Example: Binary for 4 (100) has one 1. Binary for 2 (10), obtained by shifting right once, also has one 1.
  2. Odd Numbers: If a number ends in 1 (odd), its bit count is exactly the same as (i−1)(i-1) plus that final 1, or equivalently:
    • Example: Binary for 5 (101) has two 1s. Shifting right gives 2 (10). The original number had one more set bit than i>>1i >> 1.

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 ii.

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: O(n)O(n). We iterate through each integer from 0 to num exactly once, performing constant time arithmetic operations (shift and bitwise AND).
  • Space: O(n)O(n) for the output array required by definition of the problem. The auxiliary space is O(1)O(1) 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 loop range(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 NN, Python handles integers up to standard limits efficiently without overflow issues (Python ints are arbitrary precision, though here they fit in machine words).