LeetCode 338 · Bit Manipulation · concepts: bit-manipulation, dynamic-programming

Problem

For every integer 0 … n, return the number of set bits. Aim for O(n) total.

n = 5  ->  [0,1,1,2,1,2]

Approach — DP off a shifted subproblem (optimal)

Calling popcount on each number is O(n log n). The O(n) trick uses a recurrence: i has the same bits as i >> 1 (drop the lowest bit), plus one if i is odd (that dropped bit was a 1).

def countBits(n):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)       # bits of i//2, plus the lowest bit of i
    return dp

Time O(n), space O(n).

Why the recurrence holds

i >> 1 is i with its lowest bit chopped off, so it has all of i’s set bits except possibly that lowest one. i & 1 recovers whether the chopped bit was set. Since i >> 1 < i, dp[i >> 1] is already computed — a clean overlapping-subproblem, hence DP. (An alternative recurrence, dp[i] = dp[i & (i-1)] + 1, uses Kernighan’s identity.)

Key insight

Bit counts over a range → DP, because a number’s popcount relates to a smaller number’s (i>>1 or i&(i-1)). This is a lovely bridge between bit manipulation and dynamic programming — the same result each number’s bits build on an already-solved subproblem.

↑ Back to NeetCode 150 — Solved