The DP offset approach solves this problem by observing a repeating pattern in binary numbers. Every number can be broken into two parts: the highest power of 2 it contains, and the remaining part after removing that power.

By reusing previously computed results, we avoid counting bits from scratch for every number. This turns a repetitive bit-counting problem into a clean dynamic programming solution that runs in linear time.

Intuition (simple language):
Think of binary numbers in groups. From 0 to 1, then 2 to 3, then 4 to 7, then 8 to 15, and so on.

Each group starts at a power of 2. For example:

4 (100) has exactly 1 set bit
5 (101) = 4 + 1
6 (110) = 4 + 2

So the number of set bits in i is simply:

1 + bits(i - offset)

where offset is the largest power of 2 less than or equal to i.

Step-by-step Thinking:

Create an array ans of size n + 1.
Set ans[0] = 0 because zero has no set bits.
Initialize offset = 1 (first power of 2).
Iterate i from 1 to n.
If i reaches the next power of 2, update offset.
Compute ans[i] = 1 + ans[i - offset].
Continue until all values from 0 to n are filled.

Time Complexity: O(n)
Each number from 0 to n is processed exactly once.

Space Complexity: O(n)
An array of size n + 1 is used to store results.

Learn Complexity

80. Counting Bits

Understand Before Coding

Visualize This Problem

Draw Your Approach

Example 1:

Example 2:

Learn

Topics

Companies

Hint

Use Cases