My 3ms O(n) time Java Solution


  • 0
    A
    public class Solution {
        public int[] countBits(int num) {
            int[] ret = new int[num+1];
            
            if (num == 0) return ret;
            
            ret[1] = 1;
            int mod = 1;
            for (int i=2; i<=num; i++) {
            	int remainder = i - mod;
            	if (remainder == mod) {
            		ret[i] = 1;
            		mod *= 2;
            	}
            	else {
            		ret[i] = 1 + ret[remainder];
            	}
            }
            
            return ret;        
        }
    }

Log in to reply
 

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