Counting Bits

EasyBitwise XORBlind 75JuniorOpen on LeetCodeUpdated Nov 11, 2026

You're given a non-negative integer n. Return an array ans of length n + 1 where ans[i] is the number of 1 bits in the binary form of i, for every i from 0 to n. Aim for a single O(n) pass without a built-in popcount.

Examples

n = 3 returns [0,1,1,2]

0, 1, 10, and 11 in binary have 0, 1, 1, and 2 set bits.

n = 6 returns [0,1,1,2,1,2,2]

4 is 100, 5 is 101, and 6 is 110, adding 1, 2, and 2 to the counts for 0 through 3.

n = 0 returns [0]

Only 0 is in range, and it has no 1 bits.

Constraints

0 <= n <= 10^5

Hints

Hint 1

How does the binary form of i relate to the binary form of i / 2?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Reuse answers you already have. Shifting i right by one drops its last bit, so i has the same 1 bits as i >> 1 plus one more when i is odd: ans[i] = ans[i >> 1] + (i & 1). Since i >> 1 is smaller than i, filling the array in increasing order always finds that entry ready. O(n) time, and no space beyond the output.

Time

O(n)

Space

O(1) beyond the output

Pitfall

Counting each number's bits from scratch. It gives the right answer in O(n log n), but the point of the problem is that each count follows from a smaller one in O(1).

Solutions

class Solution {
    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;
    }
}

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