338. Counting Bits

Today, I solved Counting Bits. 

 

Description:

https://leetcode.com/problems/counting-bits/description/

In this problem, we are gonna return the array. The array length should ne "n+1", and the array show how many 1 bits each number has in their binary number. 

 

Solution:

 

The length of dp array: [0] * (n + 1)

offset = 1 (This tells where the numbers between 2 ^n-1, 2^n)

 

we are gonna check the offset reach out 1, 2, 4, 8 ... each time in for loop. 

 

0 -> 0000 --- 0

1 -> 0001 --- 1 + dp[n-1] [1]

2 -> 0010 --- 1 + dp[n-2] [1]

3 -> 0011 --- 1 + dp[n-2] [2]

4 -> 0100 --- 1 + dp[n-4] [1]

5 -> 0101 --- 1 + dp[n-4] [1]

6 -> 0110 --- 1 + dp[n-4] [2]

7 -> 0111 --- 1 + dp[n-4] [3]

8-> 1000 --- 1 + dp[n-8] [1]

 

We can see the end of two bits reply 00 -> 01 -> 10 -> 11

So, we can use that, changing the offset of number.