Teaching Kids Programming – Dynamic Programming Algorithm to Count Bits for N Integers

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Example 1:
Input: 2
Output: [0,1,1]

Example 2:
Input: 5
Output: [0,1,1,2,1,2]

Follow up:
It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) / possibly in a single pass?
Space complexity should be O(n).
Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

Bruteforce Algorithm to Count Bits for N Integers

The easiest implementation would be to bruteforce. We need a function to count the number of 1’s in an integer, which can be done in quite a few ways. For example:

1
2
3
4
5
6

def count1(n):
  ans = 0
  while n > 0:
    ans += n & 1
    n >>= 1
  return ans

def count1(n):
  ans = 0
  while n > 0:
    ans += n & 1
    n >>= 1
  return ans

This takes O(LogN) time – and we can remove the rightmost 1 which will be a bit quicker:

1
2
3
4
5
6

def count1(n):
  ans = 0
  while n > 0:
    ans += 1
    n &= (n - 1)
  return ans

def count1(n):
  ans = 0
  while n > 0:
    ans += 1
    n &= (n - 1)
  return ans

This is also O(LogN) time. We can do it in Pythonic function bin() which converts an integer to binary string e.g. “0b111”

1
2

def count1(n):
  return bin(n)[2:].count("1")

def count1(n):
  return bin(n)[2:].count("1")

However, this is a bit slower which has complexity O(logN*logN)

Combined with N iterations the above algorithms takes complexity O(NLogN) for the first two, and the last one takes O(N*LogN*LogN)

1
2
3
4
5
6

class Solution:
    def countBits(self, num: int) -> List[int]:
        bits = [0]
        for i in range(1, num + 1):
            bits.append(count1(i))
        return bits

class Solution:
    def countBits(self, num: int) -> List[int]:
        bits = [0]
        for i in range(1, num + 1):
            bits.append(count1(i))
        return bits

Dynamic Programming Algorithms to Count Bits for N Integers

We can certainly do better than O(NLogN) by using the Dynamic Programming Algorithm. The key spirit here is to re-use the number of the bits that we already know for previous calculation. For example, for current calculation for integer i we can add 1 bit to i&(i-1) which is smaller than i and has been previously calculated.

1
2
3
4
5
6

class Solution:
    def countBits(self, num: int) -> List[int]:
        bits = [0]
        for i in range(1, num + 1):
            bits.append(bits[i & (i - 1)] + 1)
        return bits

class Solution:
    def countBits(self, num: int) -> List[int]:
        bits = [0]
        for i in range(1, num + 1):
            bits.append(bits[i & (i - 1)] + 1)
        return bits

Similarly, we can shift current integer i one position to the right, and add 0 or 1 bit depending on the Least Significant Bit:

1
2
3
4
5
6

class Solution:
    def countBits(self, num: int) -> List[int]:
        bits = [0]
        for i in range(1, num + 1):
            bits.append(bits[i >> 1] + (i & 1))
        return bits

class Solution:
    def countBits(self, num: int) -> List[int]:
        bits = [0]
        for i in range(1, num + 1):
            bits.append(bits[i >> 1] + (i & 1))
        return bits

We can also do it via the highest bit:

1
2
3
4
5
6
7
8
9

class Solution:
    def countBits(self, num: int) -> List[int]:
        bits = [0]
        highBit = 0
        for i in range(1, num + 1):
            if i & (i - 1) == 0:
                highBit = i
            bits.append(bits[i - highBit] + 1)
        return bits

class Solution:
    def countBits(self, num: int) -> List[int]:
        bits = [0]
        highBit = 0
        for i in range(1, num + 1):
            if i & (i - 1) == 0:
                highBit = i
            bits.append(bits[i - highBit] + 1)
        return bits

All these Dynamic Programming Algorithms take O(N) time.

See also: C++ Coding Exercise – Counting Bits using Dynamic Programming

–EOF (The Ultimate Computing & Technology Blog) —