LeetEye LeetEye
Easy Bit Manipulation ~5 min

Counting Bits

bit-manipulation counting-bits

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.

Examples

Example 1
Input: n = 2
Output: [0,1,1]
0=0, 1=1, 2=10
Example 2
Input: n = 5
Output: [0,1,1,2,1,2]
0=0, 1=1, 2=10, 3=11, 4=100, 5=101
Key Insight

DP: bits(i) = bits(i >> 1) + (i & 1)

DP: dp[i] = dp[i >> 1] + (i & 1). Right shift gives count without last bit, add 1 if last bit is set.

How to Approach This Problem

Pattern Recognition: When you see keywords like counting bits bit-manipulation, think Bit Manipulation.

Step-by-Step Reasoning

1 i >> 1 (right shift by 1):
Answer: Halves i (integer division by 2)
Right shift by 1 = divide by 2. Removes rightmost bit.
2 bits(i) compared to bits(i >> 1):
Answer: Differs by at most 1
i >> 1 loses one bit (rightmost). If that bit was 1, count decreases by 1.
3 bits(i) = ?
Answer: bits(i >> 1) + (i & 1)
bits(i>>1) gives count without last bit. Add (i & 1) for the last bit.
4 bits(0) = ?
Answer: 0
0 has no 1-bits.
5 To compute bits(i), we need:
Answer: bits(i >> 1) (which is < i)
i >> 1 < i for i > 0. So compute in order 0, 1, 2, ..., n.

Solution

def countBits(n: int) -> List[int]:
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)
    return dp

Complexity Analysis

Time O(n)
Space O(n)

Master This Pattern

Build intuition with interactive MCQs. Practice Bit Manipulation problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye