We aim to calculate the number of set bits (1s) for each number from 0 to n. We can leverage dynamic programming to solve this problem efficiently by building upon the results of previously computed values.

This approach avoids the need to repeatedly count set bits for each number individually, resulting in a more optimized solution.

Intuition:

The core idea is that we can determine the number of set bits in a number by relating it to a smaller number. Specifically, we observe a pattern related to powers of 2. Each time we encounter a power of 2 (e.g., 1, 2, 4, 8...), it essentially resets a cycle. Numbers after that power of 2 can be expressed as the power of 2 plus a smaller number.

For example, 5 (101 in binary) can be seen as 4 (100) + 1 (001). The number of set bits in 5 is the number of set bits in 1 plus 1 (for the set bit in 4). This pattern allows us to use previously computed values to derive new ones efficiently.

Step-by-step thinking:

Initialize a DP array: Create an array `dp` of size `n + 1` and initialize all its elements to 0. `dp[i]` will store the number of set bits in the number `i`.
Handle the base case: `dp[0]` is already initialized to 0, as the number 0 has no set bits.
Iterate from 1 to n: Iterate through the numbers from 1 to `n`, calculating the number of set bits for each number.
Identify the offset: Maintain an `offset` variable, which represents the largest power of 2 less than or equal to the current number `i`. This offset helps us relate the current number to a smaller number for which we have already calculated the number of set bits.
Update the offset: If the current number `i` is a power of 2 (i.e., `offset * 2 === i`), update the `offset` to `i`.
Calculate set bits using the offset: The number of set bits in `i` is 1 (for the most significant bit, which is the power of 2 represented by the offset) plus the number of set bits in `i - offset`. Therefore, `dp[i] = 1 + dp[i - offset]`.
Return the DP array: After iterating through all the numbers, return the `dp` array, which contains the number of set bits for each number from 0 to `n`.

Time Complexity: O(n)
Space Complexity: O(n)

Learn Complexity

48. Count Bits

Understand Before Coding

Visualize This Problem

Draw Your Approach

Example 1:

Example 2:

Constraints:

Learn

Topics

Hint

Use Cases