A naive brutal force solution and its implementation


  • 0
    W
    • I notice that there are already some awesome posts, with or without detailed explanation. Some are even very precise and beautiful.

    • I would like to share my thinking process and a rather length code. But the complexity is just the same as the best answer.

    • So after writing down some digits, we can find the following pattern:

    0 || 1 || 1, 2 || 1 2, 2 3 || 1 2 2 3, 2 3 3 4 || 1 2 2 3 2 3 3 4, 2 3 3 4 3 4 4 5 || ...

    • so each period is just previous period followed by previous period + 1.

    My solution involves separating num into these periods (log space), and then looping through each period to get the number from previous period. Break in the middle if the index exceeds the max range.

    class Solution {
    public:
        // range is 2 to the power n, accumulative: 1, 1, 2, 4, 8, 16, ...
        // current period is equal to previous perod followed by pervious period + 1
        // which makes current period double in size
        vector<int> countBits(int num) {
            vector<int> res(num+1, 0);
            if (num == 0) return res;
            res[1] = 1;
            if (num == 1) return res;
            
            int writeId = 2;
            for (int i = 1; pow(2, i) <= num; ++i)
            {
                while (writeId < pow(2, i+1))
                {
                    for (int j = 0; j < pow(2,i-1); ++j)
                    {
                        res[writeId] = res[writeId - pow(2,i-1)];
                        writeId++;
                        if (writeId == num+1) return res;
                    }
                    for (int j = 0; j < pow(2,i-1); ++j)
                    {
                        res[writeId] = res[writeId - pow(2,i-1)]+1;
                        writeId++;
                        if (writeId == num+1) return res;
                    }
                }
            }
            return res;
        }
    };

Log in to reply
 

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