LeetCode 338 - Counting Bits

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1’s in the binary representation of i.

example:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

How can we solve this problem?

這題要我們解決的問題是給定一個數字n,回傳0 - n中每個數字包含了多少個為1的bits。例如: n=2 => 00,01,10,回傳的結果便會是[0,1,1]。

Bit Operation approach

這裡我們可以透過bit operation AND 來解決這個問題。從Truth Table中:

我們可以到只有1AND1才會是True,所有我們只需要對每一個bit與當前counter的值做AND,如果為1就bitCounter++就可以計算出每一個值的bits的數目。
因為一個Int類型為4BYTE,包含了32個bits,所以對於[0,n]中每一個數字都必須做32次的LOOP,因此Time Complexity是O(32N)。

Solution:

class Solution {
public:
    vector<int> countBits(int n) {
        for(int i = 0;i<n+1;i++){
            int temp = 0;
            for(int j = 0;j<=31;j++){
                if( (1 << j) & i) temp++;
            }
            res[i]=temp;
        }
        return res;
    }
};

Dynamic Programming approach

我們可以先觀察一下每個數字的Binary,以n=8為例:

從圖中我們可以看得到只有1個bit為1的數字都是2ⁱ,而我們所需要計算的[2ⁱ , 2ⁱ⁺¹-1]之間的數字的數目即可。 但是,我們要怎麼計算呢?
首先,我們需要知道怎麼計算[2ⁱ , 2ⁱ⁺¹-1]裡面的bits的數目,然後我們在觀察一下Binary: 如下圖: 我們可以發現[2ⁱ , 2ⁱ⁺¹-1]都會想相隔2ⁱ-1個，也就是說我們只需要定義一個變數j作為offset 就可以移動到需要計算數字的位置( 0 <= j <= 2ⁱ-1 )。例如: i=2(2² = 4),2+0(2),2+1(3)。

接下來,我們可以透過DP來幫助我們計算。
定義BASE CASE:

DP[0] = 0 //number 0 不包含任何1’s

根據目前2ⁱ,求出DP[2ⁱ+j] = DP[j],直到計算到(n)
注意: i 會根據i是否到達2ⁱ,最後進行Left-Shift(Double自己)
注意: j 作為[0,2ⁱ)的指標

例如:
DP[1] = DP[0] + 1 //比DP[0] 多一Bits
DP[2] = DP[0] + 1 //比DP[0] 多一Bits => 也可以視為在2的區間的1, DP[1] = DP[2] = 1
DP[3] = DP[1] + 1 //比DP[1] 多一Bits DP[4] = DP[0] + 1 //比DP[1] 多一Bits

Solution:

class Solution {
public:
    vector<int> countBits(int n) {
        //Trying to use DP
        vector<int> dp(n + 1); //from 0 to n
        dp[0] = 0; //base case
        int bits = 1; //2^0 = 1
        int i = 0;
        while(bits <= n){
            //bits will be pow of 2 ->1,2,4,8,16,24
            while(i<bits && i + bits <= n){
                dp[i + bits] = dp[i] + 1;
                i++;
            }
            i = 0;
            bits = bits << 1; //double bits value
            // cout << bits;
        }
        
        return dp;
    }
};