"Easy" O(n*sizeof(integer)) solution


  • 0
    Q

    The problem description notes that "It is very easy to come up with a solution with run time O(n*sizeof(integer))."

    This is an example of one such solution (in C). Another other examples of similar solutions?

    int* countBits(int num, int* returnSize) {
        // Set the return size and allocate the array.
        *returnSize = num + 1;
        int *counts = malloc(sizeof(int) * (*returnSize));
    
        for (int n = 0; n <= num; n++) {
            counts[n] = 0;
            // From least-significant bit to most significant bit.
            int numPositions = sizeof(int) * 8;
            for (int pos = 0; pos < numsPositions; pos++) {
                int bit = 1 << pos;
                if (n & bit) {
                    // The bit in the this position is set;
                    // add to the count for this number.
                    counts[n]++;
                }
            }
        }
        return counts;
    }
    

Log in to reply
 

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