How do you solve Counting Bits?

Initialize a dp array of size n+1 with zeros and an offset variable set to 1. Iterate from 1 to n, updating offset when i reaches twice its value. For each i, dp[i] = 1 + dp[i - offset]. This builds the solution incrementally using previously computed results, achieving O(n) time and space complexity.

Counting Bits

Q: What is the time complexity of Counting Bits?

O(n). Each number from 1 to n is processed once, and each dp lookup is O(1), resulting in linear time complexity.

Q: What pattern does Counting Bits use?

The Pattern: Dynamic Programming (Bit Manipulation) The Heuristic: When counting set bits for a range of numbers, exploit the relationship between a number and the largest power of two less than or equal to it to build results incrementally, avoiding repeated bit counting.

Easy Dynamic Programming

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.

0 ≤ n ≤ 10⁵

Example

Input: n = 5

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

The algorithm initializes an array dp of length 6 with zeros. It uses an offset variable to track the most recent power of two. For i=1, offset=1, dp[1] = 1 + dp[0] = 1. For i=2, offset updates to 2 (since 2 == 2*1), dp[2] = 1 + dp[0] = 1. For i=3, dp[3] = 1 + dp[1] = 2. For i=4, offset updates to 4, dp[4] = 1 + dp[0] = 1. For i=5, dp[5] = 1 + dp[1] = 2. This approach efficiently builds the count of set bits for each number by referencing previously computed results.

Approach

Straightforward Solution

A naive approach counts the set bits for each number individually by checking each bit, resulting in O(n log n) time complexity, which is inefficient for large n.

Core Observation

The number of set bits in a number can be derived from the number of set bits in a smaller number plus one, specifically by subtracting the largest power of two less than or equal to the number.

Path to Optimal

Preview

Recognizing that numbers between powers of two share a pattern allows the use of dynamic programming…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Initialize a dp array of size n+1 with zeros and an offset variable set to 1. Iterate from 1 to n, updating offset when i reaches twice its value…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each number from 1 to n is processed once, and each dp lookup is O(1), resulting in linear time complexity.

Space

O(n)

The dp array stores the count of set bits for all numbers from 0 to n, requiring O(n) auxiliary space.

Pattern Spotlight

Dynamic Programming (Bit Manipulation)

When counting set bits for a range of numbers, exploit the relationship between a number and the largest power of two less than or equal to it to build results incrementally, avoiding repeated bit counting.

Solution

Python

1class Solution:
  def countBits(self, n: int) -> list[int]:
      dp = [0] * (n + 1)
      offset = 1
      for i in range(1, n + 1):
          if offset * 2 == i:
              offset = i
          dp[i] = 1 + dp[i - offset]
      return dp

Step-by-Step Solution

Initialize DP Array and Offset Tracker

3dp = [0] * (n + 1)
4offset = 1

Objective

To prepare storage for the count of set bits for all numbers up to n and track the current largest power of two.

Key Insight

Initializing the dp array with zeros provides a base case for zero, which has zero set bits. The offset variable starts at 1, representing the smallest power of two, and will be updated dynamically as the iteration progresses to reflect the current range segment.

Interview Quick-Check

Core Logic

The dp array stores precomputed counts of set bits, enabling O(1) retrieval for subproblems.

State & Boundaries

Offset starts at 1 because 1 is the smallest power of two and serves as the initial reference point.

Iterate Through Numbers and Update Offset

To traverse each number from 1 to n, updating the offset when a new power of two is reached.

Compute Set Bits Count Using DP Relation

To calculate the number of set bits for the current number based on the offset and previously computed results.

Return the Completed DP Array

To output the array containing the count of set bits for all numbers from 0 to n.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 8 Critical

dp[i] = 1 + dp[i - offset]

Compute dp[i] as 1 plus dp[i - offset], counting the set bits for i.

This line embodies the core dynamic programming relation: the number of set bits in i equals one (for the highest power of two bit) plus the number of set bits in the remainder (i - offset), enabling O(1) computation per number and O(n) overall.

Line 6 Critical

if offset * 2 == i:

Check if i has reached the next power of two by comparing with offset * 2.

Updating offset precisely when i equals offset * 2 ensures that the dp relation uses the correct base for counting set bits, preserving correctness and enabling the incremental computation.

Full line-by-line criticality + rationale for all 7 lines available on Pro.

Test Your Understanding

Why does updating the offset when i equals offset * 2 correctly identify the largest power of two less than or equal to i?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Counting Bits from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Counting Bits drill

or drill a free problem

1	`class Solution:`
2	`def countBits(self, n: int) -> list[int]:`
3	`dp = [0] * (n + 1)`
4	`offset = 1`
5	`for i in range(1, n + 1):`
6	`if offset * 2 == i:`
7	`offset = i`
8	`dp[i] = 1 + dp[i - offset]`
9	`return dp`