You can find the number of ones in the binary representation using the following relationship. If the number is a power of 2, there is only a single one in the binary rep. Otherwise, find the largest power of two smaller than the current number and the difference between the 2-power and our number. We will have already solved the problem for the difference so we can just look it up. For instance, suppose the number is 7 and we have already figured out the solutions for all numbers up to seven (i.e [0,1,1,2,1,2,2]. Therefore, we can consider 7 as the sum of 4 (largest 2-power smaller than 7) and 3 (the difference). Since 4 is a 2-power, we know it takes up a single one, and we already have the solution for 3. 1 + ans = 1 + 2 = 3 ones in the binary representation of 7.
if num == 0: return  ans = [0 for i in range(num+1)] prev = 0 cur = 1 for i in range(1,num+1): if i == cur: ans[i] = 1 prev = cur cur = 2*cur else: ans[i] = (1 + ans[i-prev]) return ans