Java DP solution, easy to understand


  • 0
    M
    We can easily notice that:
    
    0    0  
    1    1
    
    2    1 0
    3    1 1
    which are previous results from 0 to 1 prepended by 1, with a block size of 2.
    
    4    1 00
    5    1 01
    6    1 10
    7    1 11
    which are previous results from 0 to 3 prepended by 1, with a block size of 4.
    
    so all later numbers can be easily "looked up" from previous numbers, it's typical dp problem.
    
    
    public class Solution {
        public int[] countBits(int num) {
            if (num == 0) return new int[]{0};  //special case first
            int[] result = new int[num+1];
            result[0]=0;
            int size = 1; //block size
            int count =0;
            for(int i =1; i<= num;i++){
                result[i] = result[i-size]+1;   // find the number without leading 1, then plus 1 as current value
                if(++count == size){  //if we count reached block limit
                    size*=2; //block size doubled
                    count=0; //reset count
                }
            }
            return result;
        }
    }

  • 0
    M
    nice one thank you. I came up with shorter version of it using your 
    
    public int[] countBits(int num) {
    	int[] counts = new int[num + 1];
    	counts[0] = 0;
    	int size = 1;
    	for (int i = 1; i <= num; i++) {
    		counts[i] = counts[i - size] + 1;
    		if ((i & (i + 1)) == 0) {
    			size = size << 1;
    		}
    	}
    	return counts;
    }
    

Log in to reply
 

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