Another method && Brief summary

  • 0


    1. Intuition

      As question mentions:

      Time complexity should be O(n), Space complexity should be O(n)

      That means we must obtain results for each number in O(1) times. This reminds us that there must be some formulas or regular rules behind numbers, or else we could not get results just in such time complexity.

    2. methods (welcome to add new methods)

      First I will introduce my own different method, and then make a summary on other top votes methods.

      (1) Consider relationship between num[i], num[i-1]

      First I give recursive formula for this relationship:

         k = (int)(Math.log(i&(-i))/Math.log(2));
         ans[i] = ans[i-1] - (k-1);
         // k denotes number of consecutive 1‘s exist in the tail of i - 1

    Futher explanation:

         num   bit
         11   1011
         12   1100

    Because num[i] = num[i-1] + 1, by seeing Add process in bit-wise mode, we could find that num of 1's changes due to carry bit. That is to say, if no carry happens, num of 1's would not change. Futher more, carry happens only when consecutive 1‘s exist in the tail of number, such as 11 in 1011.

    We could convert the original problem to this one: find maxinum consecutive 1‘s in the tail of given number. To deal with this, notice that n&(-n) gives us the information about the last 1's position,

    Thus, for a given number i, first we calculate (i+1) & (-(i+1)) to obtain the last 1's position of i + 1, assume k, and then we could know the number of consecutive 1‘s in tail of i is k.

    From i to i+1, number of 1's changes (k-1) (think why?), do it recursively.

    (2) Consider relationship between num[i], num[i/2]

         ans[i] = ans[i / 2] + i % 2
      For more explanation, see **[Three-Line Java Solution][1]**

    (3) Consider relationship between num[i], num[i&(i-1)]

        ans[i] = ans[i&(i-1)] + 1
     For more explanation, see **[Easy Understanding DP & Bit Java Solution][2]**

    (4) DP methods's essential is to find recursive formula, the same as before.

    1. Code (Only my method)
        class Solution {
        public int[] countBits(int num) {
        	int[] ans = new int[num + 1];
            ans[0] = 0;
            for(int i = 1; i <= num; i++){
                //consecutive 1‘s  in previous number
            	int k = (int)(Math.log(i&(-i))/Math.log(2));
            	ans[i] = ans[i-1] - (k-1);
        	return ans;

Log in to reply

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