https://leetcode.com/problems/counting-bits

This problem is to combine dynamic programming and bit manipulations. Let us consider the example of n = 13. First create dp table and fill it with zeros. Then:

  1. Number 1 = 1 we can say, that it have 1 non-zero bit.
  2. Numbers 2 = 10, 3 = 11 have two digits in binary representation and first of them is equal to 1, so to count number of non-zero bits in this numbers, we subtract 2 from them and look into cells 0 = 00 and 1 = 01 of our table.
  3. Numbers 4 = 100, 5 = 101, 6 = 110, 7 = 111 have three digits in binary representation, so we need to look into cells 0 = 000, 1 = 001, 2 = 010 and 3 = 001.
  4. Finally for numbers 8 = 1000, 9 = 1001, 10 = 1010, 11 = 1011, 12 = 1100, 13 = 1101 we look into cells 0 = 0000, 1 = 0001, 2 = 0010, 3 = 0011, 4 = 0100, 5 = 0101. Note, that we need to interrupt earlier here, because we reached the end of our list.

Complexity We build our table in such way, that we do it in O(1) for each cell. So, both time and memory is O(n).

class Solution:
    def countBits(self, num):
        dp = [0] * (num + 1)
        for pow in range(0, 32):
            start, end = 1<<pow, 1<<(pow + 1)
            if start > num: break

            for j in range(start, min(num+1,end)):
                dp[j] = dp[j-start] + 1
        return dp

If you like the solution, you can upvote it on leetcode discussion section: Problem 0338