## Counting Bits

###### DESCRIPTION (credit Leetcode.com)

Write a function that, given an integer n, returns an array dp of size n + 1, where dp[i] stores the count of '1' bits in the binary form of i.

###### EXAMPLES

Input:

`n = 6`

Output:

`[0,1,1,2,1,2,2]`

Explanation:

```
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
6 --> 110
```

This problem is intended to give you practice with implementing a **bottom-up** dynamic programming solution.

Hint: Recurrence Relationship

To figure out the appropriate recurrence relationship, let's consider the binary representation of a number.

For example, we can split the number 9 in binary into two parts: the least significant bit (rightmost bit) and the rest of the bits. The rest of the bits are highlighted in green below, and is equal to 9 // 2 = 4 in binary.

For the number 8, the rest of the bits is also equal to 8 // 2 = 4 in binary.

In general, the "rest of bits" of any number i is equal to i // 2. Try to use that information to figure out the recurrence relationship.

In other words, assume you know the number of 1's in the binary representation of i // 2. How can you use that information to calculate the number of 1's in the binary representation of i?

Run your code to see results here

## Explanation

This solution uses a **bottom-up** dynamic programming approach to solve the problem.

The key to this problem lies in the fact that any binary number can be broken down into two parts: the least-significant (rightmost bit), and the rest of the bits. The rest of the bits can be expressed as the binary number divided by 2 (rounded down), or i >> 1.

For example:

- 4 in binary = 100
- rightmost bit = 0
- rest of bits = 10, which is also (4 // 2) = 2 in binary.

When the number is odd,

- 5 in binary = 101
- rightmost bit = 1
- rest of bits = 10, which is also (5 // 2) = 2 in binary.

If we know the number of 1's in the binary representation of i // 2, then the number of 1's in the binary representation of i is that number plus 1 if the rightmost bit is 1. We can tell if the last significant bit is 1 by checking if it is odd.

As an example, we know that the number of 1's in 2 is 1. This information can be used to calculate the number of 1's in 4. The number of 1's in 4 is the number of 1's in 2 plus 0, because 4 is even.

This establishes a **recurrence relationship** between the number of 1's in the binary representation of i and the number of 1's in the binary representation of i // 2: if count[i] is the number of 1's in the binary representation of i, then count[i] = count[i // 2] + (i % 2).

With the recurrence relationship established, we can now solve the problem using a **bottom-up** dynamic programming approach. We start with the base case dp[0] = 0, and then build up the solution for dp[i] for i from 1 to n.

def count_bits(n):dp = [0] * (n + 1)for i in range(1, n + 1):dp[i] = dp[i // 2] + (i % 2)return dp

## Solution

def count_bits(n):dp = [0] * (n + 1)for i in range(1, n + 1):dp[i] = dp[i // 2] + (i % 2)return dp

Loading comments...