Java O(n) solution


  • 0
    B
        public int[] countBits(int num) {
            int[] ret = new int[num + 1];
            if(num == 0)
                return ret;
            if (num == 1) {
                ret[1] = 1;
                return ret;
            }
            ret[1] = 1;
            int prevD = 0; int prevR = 1;
            for(int i = 2; i <= num; i++) {
                if (prevR == 1) {
                    prevR = 0;
                    prevD++;
                } else {
                    prevR = 1;
                }
                ret[i] = ret[prevR] + ret[prevD];
            }
            return ret;
        }
    }````````

Log in to reply
 

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