Easy understanding Java solution with explanation


  • 0
    public int[] countBits(int num) {
        int[] result = new int[num+1];
        if(num > 0) result[1] = 1;
        if(num > 1) result[2] = 1;
        if(num > 2) result[3] = 2;
        int prev = 2, count = 0, round = 0;
        for(int i=4; i<=num; i++) {
            result[i] = result[prev+count]+round;
            count++;
            if(count == prev) round = 1;
            if(count == prev * 2) {
                round = 0;
                count = 0;
                prev  = i - 2 * prev + 1;
            }
        }
        return result;
    }
    

    main idea

    index: 00 01 | 02 03 | 04 05 06 07 | 08 09 10 11 12 13 14 15
    value: 00 01 | 01 02 | 01 02 02 03 | 01 02 02 03 02 03 03 04

    From index 4, we can divide array into multiple groups, each group has 4, 8, 16, 32 ... elements; each group can also divide into two parts, values in the first part is exactly the same as the previous group, and values in the second part is the values of the first part plus 1.


Log in to reply
 

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