Java 4ms solution space O(1) as it uses just the previous number for finding 1's


  • 0
    S

    Using Odd and Even :

         public class Solution {
                public int[] countBits(int n) {
                    int[] result = new int[n+1];
            		result[0] = 0;
            		if(n > 0){
            		   result[1] = 1; 
            		}
            		if(n < 2){
            		    return result;
            		}
            		
            		for(int i = 2; i < n+1; i++){
            		    result[i] = result[i-1] + 1 ;
            		    /* 
            		    for even numbers , decrement the count of trailing 1's eg for 8 :
                        previous number ( 7 = 111 ) , has count of 1 = 3 ,
            		    in 8 = 1000 
            		    count of 1's in 8 = count of 1's in 7 + 1 - 3 (where 3 is trailing 1's in seven)
            		    */
            			if((i & 1) == 0){
            				int temp = i-1;
            				while((temp & 1) == 1){
            					result[i]--;
            					temp = temp >> 1;
            				}
            			}
            		}
            		return result;
                }
            }

Log in to reply
 

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