My java solution 10ms using dynamic programming, O(n) runtime, O(n) space complexity


  • 0
    S
    public class Solution {
        public int[] countBits(int num) {
            
            if (num < 2){
                return num == 0 ? new int[]{0} : new int[]{0,1};
            }
            
            int[] counts = new int[num+1]; //array to hold results
            
            //base case
            counts[0] = 0;
            counts[1] = 1;
            
            int setIndex = 2; //index will keep track of each number range. a number range starts at a power of 2 (such as 2^1)
                                //each particular power of 2^i, the number range will contain 2^i numbers
                                
                                
            int iteration = 0; //keeps track the current number range being iterated over
            
            while (setIndex < counts.length){
                
                
                int currPointer = setIndex; //keep pointer to current index of the range you are iterating over
                
                //the first half of numbers in a set will have the same value as the first half of the numbers in the previous set
                for (int i = setIndex; i < setIndex/2+setIndex && i < counts.length; i++){
                    counts[i] = counts[i-((int)Math.pow(2, iteration))]; //gets the values of the first half of the previous range
                    currPointer++;
                }
                
                //the second half of numbers in a set will have the values of the numbers in the first half of the set incremented by 1
                for (int j = currPointer; j <= setIndex*2-1 && j < counts.length; j++){
                    counts[j] = counts[j-setIndex/2] + 1;  //get the values of 
                    currPointer++;
                }
           
                //update set index to be index of next power of 2 set
                //increase the pointer of the current number range iteration
                setIndex = currPointer;
                iteration++;
            }
            
            return counts;
            
        }
    }

Log in to reply
 

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