# The Bit Ladder

> Count the ones all the way up.

Canonical URL: <https://datadriven.io/problems/the_bit_ladder>

Domain: Python · Difficulty: easy · Seniority: L3

## Problem

Given non-negative integer n, return a list of length n+1 where position i is the count of 1-bits in i.

## Worked solution and explanation

### Why this problem exists in real interviews

Computing bit counts for 0 through n tests **dynamic programming on bit patterns**. The DP recurrence `count[i] = count[i >> 1] + (i & 1)` is an elegant insight that avoids recomputing from scratch for each number.

> **Trick to Solving**
>
> The number of 1-bits in `i` equals the number of 1-bits in `i >> 1` (everything except the last bit) plus `i & 1` (the last bit itself). This gives an O(n) solution using previously computed results.

---

### Break down the requirements

#### Step 1: Initialize a result list of size n+1

We need counts for every integer from 0 to n inclusive.

#### Step 2: Apply the DP recurrence

For each i from 1 to n: `result[i] = result[i >> 1] + (i & 1)`.

---

### The solution

**DP bit counting using right-shift recurrence**

```python
def count_bits_range(n):
    result = [0] * (n + 1)
    for i in range(1, n + 1):
        result[i] = result[i >> 1] + (i & 1)
    return result
```

> **Time and Space Complexity**
>
> **Time:** O(n). Each value from 0 to n is computed in O(1) using the precomputed table.
> 
> **Space:** O(n) for the result array.

> **Interviewers Watch For**
>
> The DP insight. A naive approach that calls a bit-counting function for each number is O(n log n). The DP approach is strictly O(n).

> **Common Pitfall**
>
> Not recognizing the DP recurrence and instead writing a nested loop that counts bits from scratch for each number.

---

## Common follow-up questions

- Can you explain why the recurrence works? _(Tests understanding that `i >> 1` strips the last bit, so adding `i & 1` accounts for it.)_
- How would you verify your DP result? _(Tests using `bin(i).count('1')` as a brute-force validation.)_
- What if n is very large and you need memory efficiency? _(Tests computing on-the-fly using the shift-and-mask approach for each number individually.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_bit_ladder)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.