Java O(n) solution implementing hints


  • 0
    R
    public int[] countBits(int num) {
        int[] ans = new int[num + 1];
        for (int i = 1; i < num+1; )
        {
            for (int j = 0, k = i; j < k && i < num + 1; j++, i++)
            {
                ans[i] = ans[j] + 1;
            }
        }
        return ans;
    }
    

    0 = 00

    1 = 01

    2 = 10

    3 = 11

    2,3 are the same with 0,1 in lowest digit, just add 1 to the result of 0, 1, then we can get result for 2,3.

    Same for [4,7] and [0,3], [8,15] and [0,7]. It can go on and on.


Log in to reply
 

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