Leetcode 338. Counting Bits (Python)

Related Topic

Dynamic-Programming.

Description

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Sample I/O

Example 1

Input: 2
Output: [0,1,1]

Example 2

Input: 5
Output: [0,1,1,2,1,2]

Note:

• It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
• Space complexity should be O(n).
• Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

Methodology

This question solved by Dynamic Programming.

1. The DP pattern That insparied me like below:

   Base case
    0: 0 -> 0

    when 2^0
    1: 1 -> 1

    when 2^1
    2: 10 -> 1
    3: 11 -> 2

    when 2^2
    4: 100 -> 1
    5: 101 -> 2
    6: 110 -> 2
    7: 111 -> 3

    when 2^3
    8: 1000 -> 1
    9: 1001 -> 2
    10: 10010 -> 2
    .
    .
    .

1. Find the pattern:

   From the above pattern, when the num reach to 2^(num-1), all the num in the range[2^(num-1), 2^(num)-1] can find it’s 1 to 1 matched value from [0, 2^(num-1)-1]. You can use modulo or divide method to implement that.

Code

def countBits(self, num: int) -> List[int]:
        coef = 1
        dp=[0]*(num+1)
        for i in range(1,num+1):
            if i == coef*2:
                coef*=2
            dp[i] = dp[i%div]+1
        return dp

BigO

We only iterate the dp list, so the time and spact complexity is O(n).