# LeetCode 338: Counting Bits — Step-by-Step Visual Trace

**Easy** — Dynamic Programming | Bit Manipulation | Array

## The Problem

Given an integer n, return an array where the i-th element represents the number of 1-bits in the binary representation of integer i for all numbers from 0 to n.

## Approach

Use dynamic programming to build the result array incrementively. For any number i, the count of 1-bits equals the count for i//2 plus 1 if i is odd (i%2). This leverages the relationship between a number and its right-shifted version.

**Time:** O(n) · **Space:** O(n)

## Code

```python
class Solution:
    def countBits(self, num: int) -> List[int]:
        bits_count = [0] * (num + 1)

        for i in range(1, num + 1):
            bits_count[i] = bits_count[i // 2] + (i % 2)

        return bits_count
```

## Watch It Run

> **[Open interactive visualization](https://tracelit.dev/app?trace=0338_counting-bits)**

> **Try it yourself:** Open [TraceLit](https://tracelit.dev/app?trace=0338_counting-bits) and step through every line.

---

*Built with [TraceLit](https://tracelit.dev) — the visual algorithm tracer for LeetCode practice.*