Counting Bits Fast

Problem: Given a non-negative integer num, return an array where each element at index i contains the number of 1’s in the binary representation of i.

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

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

First Approach: Find the Pattern

Group numbers by powers of 2 and see if later results can be calculated from earlier ones. As N increases, the first half matches previous group counts. The second half adds one extra 1.

vector<int> countBits(int num) {
    vector<int> res = {0, 1, 1, 2};
    if (num < 3)
        return vector<int>(res.begin(), res.begin()+num+1);

    int offset=2;
    while((offset<<1) <= num) {
        for(int i=0;i<=1;++i) {
            for(int j=0;j<offset&&res.size()<=num;++j)
                res.push_back(res[offset+j]+i);
        }
        offset<<=1;
    }
    return res;
}

Second Approach: Dynamic Programming

Look closer. The count of 1’s in N relates to the count in N/2. Recurrence: count(N) = count(N»1) + (N & 1)

vector<int> countBits(int num) {
    vector<int> ret(num+1, 0);
    for (int i = 1; i <= num; ++i)
        ret[i] = ret[i&(i-1)] + 1;
    return ret;
}

#bit-manipulation #dp