5ms JAVA solution with explanation


  • 1
    J
    //Let f(k) be the number of 1's in the binary representation of k, then
    //f(k) = 1,                       if k is a power of 2
    //f(k) = f(j) + f(k - j),         otherwise
    //here j is the largest power of 2 that is no larger than k
    //based on the above equation
    //if k = 1, then f(k) = 1
    //if k = 2, then f(k) = 1
    //if k = 3, then j = 2, thus f(k) = f(2) + f(1) = 2
    //please note that i in the code is the smallest power of 2 that is no less than k
    //that is, i is the power of 2 following j
    public class Solution {
            public int[] countBits(int num) {
                int[] arr = new int[num + 1];
                if (num == 0) {
                    return arr;
                }
                int i = 1;
                int j = 1;
                for (int k = 1; k <= num; k++) {
                    if (k == i) {
                        arr[k] = 1;
                        j = i;
                        i <<= 1;
                    }
                    else {
                        arr[k] += arr[j] + arr[k - j];
                    }
                }
                return arr;
            }

Log in to reply
 

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