Share my 3ms JAVA Solution with explanation


  • 1
    Z

    Solution 1:

    As we can see:
    A[1] = A[1 - 1] + 1; --> 1 - 2^0
    A[2] = A[2 - 2] + 1; --> 2 - 2^1
    A[3] = A[3 - 2] + 1; --> 2 - 2^1
    A[4] = A[4 - 4] + 1; --> 2 - 2^2
    A[5] = A[5 - 4] + 1; ...
    A[6] = A[6 - 4] + 1; ...
    A[7] = A[7 - 4] + 1; ...

    That is because the difference between 0 and 1 is the most significant bit.
    The difference between 0 and 2 is the most significant bit, so are 1 and 3, 0 and 4, 1 and 5, 2 and 6, 3 and 7... and so on so forth.
    So we first set a offset = 2, and when i < offset, A[i] = A[i - offset / 2] + 1.
    And update offset *= 2 when i >= offset.

    public class Solution {
        public int[] countBits(int num) {
            int[] ret = new int[num + 1];
            ret[0] = 0;
            int offset = 2;
            for(int i = 1; i <= num;i++){
                if(i >= offset) offset *= 2;
                ret[i] = ret[i - offset / 2] + 1;
            }
            return ret;
        }
    }
    

    Solution 2:
    However, a more simple solution will be focusing on the least significant bit.

    0 -> 0 A[0] = 0
    1 -> 1 A[1] = 1
    2 -> 10 A[2] = 1
    3 -> 11 A[3] = 2
    4 -> 100 A[4] = 1
    5 -> 101 A[5] = 2
    6 -> 110 A[6] = 2
    7 -> 111 A[7] = 3

    As we can see:
    '100' >> 1 ==> '10' 4 & 1 = 0. So, A[4] = A[4 >> 1] + 4 & 1.
    '111' >> 1 ==> '11' 7 & 1 = 1. So, A[7] = A[7 >> 1] + 7 & 1.

    public class Solution {
        public int[] countBits(int num) {
            int[] ret = new int[num + 1];
            ret[0] = 0;
            int offset = 2;
            for(int i = 1; i <= num;i++){
                ret[i] = ret[i >>> 1] + (i & 1);
            }
            return ret;
        }
    }
    

Log in to reply
 

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