A DP solution in C


  • 12

    DP equation:

    • arr[i] == i&1? arr[i/2]+1 : arr[i/2];

    //AC - 40ms;
    int* countBits(int num, int *returnSize)
    {
        num++;
        *returnSize = num;
        int* arr = (int*)malloc(sizeof(int)*num);
        arr[0] = 0;
        for(int i = 1; i < num; i++)
            arr[i] = (i&1)? arr[i>>1]+1 : arr[i>>1];
        return arr;
    }

  • 1
    C

    it's faster;

    int* countBits(int num, int *returnSize)
        {
            num++;
            *returnSize = num;
            int* arr = (int*)malloc(sizeof(int)*num);
            arr[0]=0;
            //memset(arr, 0, sizeof(int)*num);
            for(int i = 1; i < num; i++)
                arr[i] = (i&1)? arr[i>>1]+1 : arr[i>>1];
            return arr;
    

  • 0

    Indeed, it's needless to set all elements, and only initializing the first actually saves some time from 44ms to 40ms. Thanks for your feedback!


  • 0
    K

    It's a beautiful solution.
    Thank you a lot :)


  • 0
    X

    @LHearen
    it's very clever.
    Thanks a lot!


  • 1
    S

    Very nice, I don't know if it would help, but you might consider the following:

    arr[i] = arr[i>>1] + (i&1);

  • 0

    @sganje This can do but to some extent, it loses some readability. Good idea.


  • 0
    S

    @LHearen said in A DP solution in C:

    arr[i] == i&1? arr[i/2]+1 : arr[i/2];

    Awesome as usual.


  • 0

    @Salkexy2 C++ solution is also enclosed now.

    class Solution {
    public:
        vector<int> countBits(int num) {
            vector<int> v(1,0);
            for(int i = 1; i <= num; ++i)
                v.push_back(v[i>>1]+(i&1));
            return v;
        }
    };
    

  • 0
    B

    It is a clover answer, thank you!


  • 0
    B

    And this is the python answer.

    # Runtime: 224 ms
    class Solution(object):                                                                                                          
        def countBits(self, num):  
            """                    
            :type num: int         
            :rtype: List[int]      
            """                    
            result = [0]
            for i in range(1, num + 1):     
                result.append(result[i>>1] + 1 if i&1 else result[i>>1])
            return result   
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.