Counting Number of Set Bits for N Integers using Dynamic Programming Algorithm in Linear Time

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.

Count Integer Individually

We can write a loop to count the number of bits set in a integer and this is O(n) so it would have a O(n^2) runtime complexity which is not optimal. According to this post we have a lighting fast i.e. O(1) constant complexity method to count the number of set bits using bit tweaks. So put all these together which becomes following solution:

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

class Solution {
public:
    int bitCount(int i) {
        i = i - ((i >> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
        i = (i + (i >> 4)) & 0x0f0f0f0f;
        i = i + (i >> 8);
        i = i + (i >> 16);
        return i & 0x3f;
    }    
 
    vector<int> countBits(int num) {
        vector<int> r;
        for (int i = 0; i <= num; i ++) {
            r.push_back(bitCount(i));
        }
        return r;
    }
}

class Solution {
public:
    int bitCount(int i) {
        i = i - ((i >> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
        i = (i + (i >> 4)) & 0x0f0f0f0f;
        i = i + (i >> 8);
        i = i + (i >> 16);
        return i & 0x3f;
    }    

    vector<int> countBits(int num) {
        vector<int> r;
        for (int i = 0; i <= num; i ++) {
            r.push_back(bitCount(i));
        }
        return r;
    }
}

The overall complexity is O(n) because the function bitCount is considered as O(1). This is an example to optimize O(n^2) solution to O(1) base on implementation detail, which may not be generalized to all other problems.

Dynamic Programming

We know Dynamic Programming is a powerful tool by re-using the intermediate results. We have a obvious recurrence formula here (if F(n) represents the number of bits set for integer n).

1
2
3
4

if n is even:
  F(n) = F(n/2)
else: # if n is odd
  F(n) = F(n/2) + 1 

if n is even:
  F(n) = F(n/2)
else: # if n is odd
  F(n) = F(n/2) + 1 

The above two can be combined as

So the implementation is simpler, faster and much more clean:

1
2
3
4
5
6
7
8
9
10

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> r(num + 1, 0);
        for (int i = 0; i <= num; i ++) {
            r[i] = r[i >> 1] + (i & 1);
        }
        return r;
    }
};

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> r(num + 1, 0);
        for (int i = 0; i <= num; i ++) {
            r[i] = r[i >> 1] + (i & 1);
        }
        return r;
    }
};

We can also solve this problem slightly differently. We can use n & (n – 1) to make an integer with a bit less. For example, 7 in binary is (111) so 7 & (7 – 1) = 6, which in binary is (110).

Then, we have this formula:

Plug this in then we have:

1
2
3
4
5
6
7
8
9
10

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> r(num + 1, 0);
        for (int i = 0; i <= num; i ++) {
            r[i] = r[i & (i - 1)] + 1;
        }
        return r;
    }
};

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> r(num + 1, 0);
        for (int i = 0; i <= num; i ++) {
            r[i] = r[i & (i - 1)] + 1;
        }
        return r;
    }
};

In this case, DP solutions are slightly faster than the first approach although the three methods are all O(n), one-pass solution. The first approach can be executed in parallel (e.g. via multithreading) while the DP solutions rely on computing and storing intermediate solutions so may not be easily parallelized.

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

–EOF (The Ultimate Computing & Technology Blog) —