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

  • 0
    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
                //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 
                //update set index to be index of next power of 2 set
                //increase the pointer of the current number range iteration
                setIndex = currPointer;
            return counts;

Log in to reply

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