← Back to DSA Animator
Counting Bits LC #338 Easy DP · Bit Shift
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.

Example 1
Input: n = 2
Output: [0,1,1]
Explanation: 0→0b0=0, 1→0b1=1, 2→0b10=1 bit.
Example 2
Input: n = 5
Output: [0,1,1,2,1,2]
Explanation: dp[i] = dp[i>>1] + (i&1) fills in O(n).
Constraints: 0 ≤ n ≤ 10⁵  |  Must run in O(n) and not use built-in popcount functions
Try Examples
Custom:
Approach
DP Bit Shift — dp[i] = dp[i>>1] + (i&1)
Right-shift removes the last bit (already counted). Add the last bit (i&1). Each cell is computed in O(1) from a prior result. One forward pass builds the whole array.
DP Array
Current Computation
Waiting to start...
Variables
i
—
i >> 1
—
i & 1
—
dp[i]
—
Step Logic
Press ▶ Play or Next Step to begin.
✅
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
dp[0] = 0 (base case: 0 has no set bits)
2
i >> 1 removes last bit — dp[i>>1] already known
3
i & 1 gives the last bit (0 or 1)
4
dp[i] = dp[i>>1] + (i&1) — O(1) per element
Time
O(n)
Space
O(n)
Why It Works

Every number i can be formed by taking i>>1 (dropping the last bit) and optionally adding 1 (the last bit i&1). Since i>>1 < i, dp[i>>1] is always already computed. This gives us a perfect O(1) recurrence per element — no counting, no loops, just table lookups.