DSA AnimatorDSA animations
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.

How to solve Counting Bits

LeetCode 338 · Easy · Bit Manipulation · Pattern: DP on Bits

Why the obvious approach is slow

Counting the bits of each number separately takes O(n log n). But each count can be built from a smaller number.

The key idea

Shifting i right by one drops its last bit. So i has the same bits as i shifted right, plus its last bit. That gives the rule: bits of i equals bits of i over 2, plus i AND 1. Because i over 2 is smaller, its count is already in the array.

Remember

I shifted right is i without its last bit. Dynamic programming over smaller numbers.

Run the animation above on your own input, or watch the 1:28 video explanation of Counting Bits with a dry run and Java code.

More Bit Manipulation problems