Counting Bits

Problem

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

Examples

The brute-force approach

For each i from 0 to n, count the 1 bits of i using the hammingWeight function.

result = []
for i in range(n + 1):
    result.append(bin(i).count("1"))
return result

O(n log n) — each count takes O(log i) = O(log n) time.

Spotting the pattern

This is a Bit Manipulation problem. The key question to ask yourself:

If you know the number of 1 bits in i >> 1 (i with its last bit removed), what's the relationship to the bit count of i itself?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.