EASY

Counting Bits

Given an integer n, return an array ans of length n + 1 where ans[i] is the number of 1-bits in the binary representation of i, for every i from 0 to n.

Example

Input n = 5

Output [0,1,1,2,1,2]

Key Pointers

Recomputing the bit count from scratch for every i is wasteful — reuse work already done for smaller numbers.
Dropping the lowest bit of i (i >> 1) gives a smaller number whose bit count is already in the array.
The dropped bit itself is just i & 1 — add it back to get i's full count.

Step-by-Step Analysis

Create ans as an array of n + 1 zeros.
For each i from 1 to n: set ans[i] = ans[i >> 1] + (i & 1).
i >> 1 is always smaller than i, so its answer is already filled in by the time you reach i.
Return ans once every index is filled.

Complexity

Time: O(n) — Space: O(n) for the output (O(1) extra)

Code

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

Code Explanation

How the solution above works, piece by piece.

i >> 1 is i without its last bit, a smaller number whose answer is already computed.
i & 1 is that last bit (1 if i is odd).
So ans[i] = ans[i >> 1] + (i & 1): the bits of the shorter number plus the dropped bit.
One pass, O(n) time, and no bit is counted twice.

Visual Walkthrough

Running it on n = 5:

For 5 (101): dropping the last bit gives 2 (10), which has 1 set bit; add the dropped 1 → 2.

1 bit

Video Explanation

NeetCode — Counting Bits, LeetCode 338