Blind 75Easy

Counting Bits — DP from Lowest Set Bit

Use the recurrence dp[i] = dp[i >> 1] + (i & 1) to build popcounts from 0 to n.

Dynamic ProgrammingBit Manipulation

View problem on LeetCode

Problem Statement

For every number i in range [0, n], return the number of set bits.

Why This Problem Matters

Practises combining bit operations with dynamic programming.
Generalises popcount knowledge across a range efficiently.
Common warm-up before harder DP/bit problems.

Thought Process

Observe recurrence

Right-shifting drops the lowest bit; add 1 when the dropped bit was set.

Build bottom-up array

dp[0] = 0; fill dp[i] using dp[i >> 1] + (i & 1).

Optionally use highest power of two

Alternative recurrence dp[i] = 1 + dp[i - highestPowerOfTwo].

Step-by-Step Reasoning

Initialise dp array length n + 1.
Loop i from 1..n computing dp[i] = dp[i >> 1] + (i & 1).
Return dp.

Dry Run

n = 5

dp = [0,1,1,2,1,2].

n = 0

dp = [0].

Complexity Analysis

Time

O(n)

Space

O(n)

Why

Single pass fills dp array of size n + 1.

Annotated Solution

JAVA

public class CountingBits {
  public int[] countBits(int n) {
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i += 1) {
      dp[i] = dp[i >> 1] + (i & 1);
    }
    return dp;
  }
}

Right-shifting removes the least significant bit; adding (i & 1) detects whether that bit was a one.

Common Pitfalls

Forgetting to initialise dp[0] leads to default zeros but emphasise base case explicitly.
Using recursion for each value degenerates to O(n log n).
Confusing >> with >>> changes behaviour for negative numbers; inputs are non-negative so >> is safe.

Follow-Up Questions

Can you compute counts only for odd numbers? (Observe parity pattern.)
How would you adapt this for 64-bit numbers?

Key Takeaways

DP on integers often leverages binary representations.

Look for recurrences that reuse previously computed values.

Multiple recurrences exist—mention alternatives to show depth.