Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Counting Bits

LeetCode #338Easy
dp[i] = dp[i>>1] + (i & 1)

Given an integer n, return an array of length n+1 where each entry i holds the number of set bits (1s) in the binary representation of i.

Asked atAmazonGoogle
step 1 / 11
·
·
·
·
·
·
·
·
[0][1][2][3][4][5][6][7]
DP on the last bit
▸
1def countBits(n):
2    dp = [0] * (n + 1)
3    for i in 1..n:
4        # i>>1 drops the last bit (already counted)
5        # i&1 adds that dropped bit back
6        dp[i] = dp[i >> 1] + (i & 1)
7    return dp
state
  • n7
  • recurrencedp[i] = dp[i>>1] + (i & 1)

line 1Counting Bits: for every i from 0 to n, count how many 1-bits it has in binary. The naive way pops bits per number — O(n log n). DP does it in O(n) by REUSING a smaller answer. The main row IS the dp table.