[Algorithm] Counting Bits

Counting Bits

Problem Statement:

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:
For num = 5 you should return [0,1,1,2,1,2].

Solution: Dynamic Programming

Time Complexity : O(n)
Space Complexity: O(n)

This problem can be solved easily with O(32n) by counting the bits with brutal force. But a better way is to use dynamic programming with the following observation:

Any number i can be expressed as:

(1)  i = j + 2^k, where j < 2^k

The reason we pick 2^k is that it only will have one bit which is 1 and all the rest is 0. Since j < 2^k, the number j will never have 1 bits overlapping with the number 2^k. Thus we can conclude this:

(2) bits_count[i] = bits_count[j] + bits_count[2^k], where i = j + 2^k

With (1) and (2) we can easily have the following code implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

class Solution { public: vector<int> countBits(int num) { if (num == 0) return {0}; vector<int> result(num+1); result[0] = 0; result[1] = 1; int base = 1; for (int i=2; i<=num; i++) { if (i == base*2) { result[i] = 1; base *= 2; } else { result[i] = result[base] + result[i - base]; } } return result; } };