Counting Bits medium

Description

Given a non-negative integer n, return an array ans of length n + 1 such that for each i in 0..n, ans[i] is the number of 1 bits in the binary representation of i.

Examples

> Case 1:
    Input:  n = 2
    Output: [0, 1, 1]
    # 0 = 00 → 0
    # 1 = 01 → 1
    # 2 = 10 → 1
 
> Case 2:
    Input:  n = 5
    Output: [0, 1, 1, 2, 1, 2]
    # 0 = 000 → 0
    # 1 = 001 → 1
    # 2 = 010 → 1
    # 3 = 011 → 2
    # 4 = 100 → 1
    # 5 = 101 → 2

Constraints

• 0 <= n <= 10^5
• Aim for O(n) total time — better than calling popcount on each value.

Approach 1: Call popcount n+1 times

The naive approach: for each i, count its set bits independently.

vector<int> countBits(int n) {
    vector<int> ans(n + 1);
    for (int i = 0; i <= n; i++) {
        ans[i] = __builtin_popcount(i);
    }
    return ans;
}

def count_bits(n):
    return [i.bit_count() for i in range(n + 1)]

public int[] countBits(int n) {
    int[] ans = new int[n + 1];
    for (int i = 0; i <= n; i++) ans[i] = Integer.bitCount(i);
    return ans;
}

Time: O(n log n) worst case if popcount is software (one bit per loop iteration); O(n) if it’s hardware-accelerated. Correct, but lazy. The interesting solution exploits the structure of the problem.

Approach 2: The DP insight (O(n))

We’re computing popcount(i) for every i from 0 to n — so previous answers are sitting right there to be reused. The question is: how does popcount(i) relate to a smaller already-known value?

Identity: for any i > 0, popcount(i) == popcount(i >> 1) + (i & 1).

The reason: i >> 1 drops the lowest bit, so it has the same set bits as i except possibly the bottom one. The bottom bit’s contribution is i & 1.

i = 13 = 1101

popcount(13) = popcount(6) + (13 & 1)
             = popcount(110)  + 1
             = 2 + 1
             = 3

Since 6 was computed earlier in the loop, we get the answer in O(1) per element.

vector<int> countBits(int n) {
    vector<int> ans(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        ans[i] = ans[i >> 1] + (i & 1);
    }
    return ans;
}

def count_bits(n):
    ans = [0] * (n + 1)
    for i in range(1, n + 1):
        ans[i] = ans[i >> 1] + (i & 1)
    return ans

public int[] countBits(int n) {
    int[] ans = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        ans[i] = ans[i >> 1] + (i & 1);
    }
    return ans;
}

Time: O(n), Space: O(n) for the output (unavoidable; the call doesn’t use any extra working memory).

Approach 3: Lowest-bit-trick variant

A different recurrence using Kernighan’s clear-lowest-bit identity. For i > 0, popcount(i) == popcount(i & (i - 1)) + 1 — because i & (i-1) is i with one fewer set bit.

def count_bits(n):
    ans = [0] * (n + 1)
    for i in range(1, n + 1):
        ans[i] = ans[i & (i - 1)] + 1
    return ans

Same O(n) time. Slightly more elegant if you’re already thinking in Kernighan’s framework.

Why this is a textbook DP problem

The general DP recipe: identify a recurrence that expresses each new answer in terms of a smaller, already-computed one. Here it’s f(i) = f(i >> 1) + (i & 1). Filling a table left-to-right makes every lookup O(1), and the total cost drops to O(n).

This same shape — “each new index depends on a smaller index” — appears all over DP. Counting Bits is a 5-line warmup; the same structure underlies Longest Increasing Subsequence, Coin Change, House Robber, and dozens of others.

Analysis