Problem statement

Given an integer n, return an array out of length n + 1 where out[i] is the number of 1 bits in the binary representation of i.

Example 1

Input: n = 2
Output: [0,1,1]

Example 2

Input: n = 5
Output: [0,1,1,2,1,2]

Example 3

Input: n = 0
Output: [0]

Constraints

• 0 <= n <= 40

Follow-up: Can you do it in a single pass, in O(n) time and without any built-in popcount?

Hints for Counting Bits

1. Hint 1

   Counting the bits of every number independently is O(n log n) — you can do better.

2. Hint 2

   i and i >> 1 differ only by the lowest bit of i.

3. Hint 3

   So out[i] = out[i >> 1] + (i & 1), filling the array left to right.

How to solve Counting Bits

i and i >> 1 differ only in the lowest bit, so out[i] = out[i >> 1] + (i & 1).

Approach

1. Set out[0] = 0.
2. For i from 1 to n, out[i] = out[i >> 1] + (i & 1).

Why it works

Shifting right drops the lowest bit, whose value is i & 1; the rest of the popcount was already computed for a smaller index.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• out[i] = out[i & (i - 1)] + 1 is the equivalent recurrence via the lowest set bit.

Reference solution

Python

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

Java

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

C++

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

JavaScript

var countBits = function(n) {
    const out = [0];
    for (let i = 1; i <= n; i++) out.push(out[i >> 1] + (i & 1));
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More dynamic programming problems

• Count Ways to Tile a 2 x N Floor Easy
• Divisor Game Easy
• Pascal's Triangle II Easy
• N-th Tribonacci Number Easy
• Fibonacci Number Easy
• Pascal's Triangle Easy