O(n) C soln with 128 ms


  • 1
    1
    int* countBits(int num, int* returnSize) {
        *returnSize = num+1;
        int *ret = (int *) malloc(sizeof(int)* (*returnSize));
        bzero(ret, sizeof(int) * (*returnSize));
        if (!num) return ret;
        int i, square=0;
        for(i=1;i<=num;i++) {
            if(!(i&(i-1))) {ret[i]=1; square = i;}
            else ret[i] = ret[i%square]+1;
        }
        return ret;
    }

  • 0
    B

    We may have a more concise C solution:

    int* countBits(int num, int* returnSize) {
        int* arr, mask, i;
        
        if ((arr = malloc(sizeof(int[num + 1]))) == NULL)
            return NULL;
        for (mask = 1, arr[0] = 0, i = 1; i <= num; i++) {
            if (i == (mask << 1))
                mask <<= 1;
            arr[i] = 1 + arr[i & ~mask];
        }
        *returnSize = num + 1;
        return arr;
    }

Log in to reply
 

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