Leetcode Counting Bits problem solution

In this Leetcode Counting Bits problem solution we have 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.

Problem solution in Python.

class Solution(object):
    def countBits(self, num):
        if num == 0: return [0]
        dp = [0]*(num+1)
        dp[0] = 0
        dp[1] = 1
        for i in range(2, num+1):
            if i%2 == 0: dp[i] = dp[i/2]
            else: dp[i] = 1 + dp[(i-1)/2]
                
        return dp

Problem solution in Java.

class Solution {
    public int[] countBits(int num) {
        int[] dp = new int[num+1];
        
        dp[0] = 0;
        int nearest = 0;
        for (int k = 1; k <= num; k++) {
            if ((k & (k-1)) == 0) {
                dp[k] = 1;
                nearest = k;
            } else {
                dp[k] = dp[k-nearest] + dp[nearest];
            }
        }
        
        return dp;
    }
}

Problem solution in C++.

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int>res(num+1);
        res[0] = 0;
        for(int i = 1 ; i <= num ; i++)
            res[i] = res[i/2] + (i&1);
        return res;
    }
};

Problem solution in C.

int* countBits(int num, int* returnSize) {
    int i =0,k = 4, ano = 4;
    int num1 = num;
    *returnSize = (num+1);
    int *arr = malloc(sizeof(int)*(num+1));
    if(num1>3)
        num1 = 3;
    switch(num1){
        case 3:
            arr[3] = 2;
            num--;
            num1--;
        case 2:
            arr[2] = 1;
            num--;
            num1--;
        case 1:
            arr[1] = 1;
            num--;
            num1--;
        case 0:
            arr[0] = 0;
            num--;
            break;
    }
    while(num >= 0){
        if(i>=ano) {
            ano *= 2;
            i = 0;
        }
        arr[k] = arr[i%ano] + 1;
        i++;
        k++;
        num--;
    }
    return arr;

}

coding problems