Counting Bits

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

brute Force#

For each number from 0 to n, count its set bits independently using the standard shift-right-and-check loop. This recomputes each answer from scratch without reusing previously computed values, resulting in O(n × 32) = O(n) time in practice but with redundant bit-counting work. The DP approach below avoids this by building on previously computed answers.

class Solution {
public:

    int hammingWeight(int n)
    {
        int noSetBits = 0;
        while(n)
        {
            if(n&1)
                noSetBits++;
            n = n>>1;
        }
        return noSetBits;
    }

    vector<int> countBits(int n) {
        vector<int> ans;
        ans.push_back(0);
        for(int i=1;i<=n;i++){
            ans.push_back(hammingWeight(i));
        }
        return ans;
    }
};

Time Complexity: O(n)

Space Complexity: O(n)

Dynamic Programming#

The key insight is that i >> 1 (right-shifting by 1) is just i with its last bit removed, and i & 1 is the last bit itself. So the number of set bits in i equals the number of set bits in i/2 plus the parity of i. Since i/2 < i, its bit count is already in the array by the time we compute index i. This one-liner recurrence processes each number in O(1) and fills the entire array in O(n) total with no redundant work.

class Solution {
public:

    vector<int> countBits(int n) {
        vector<int> ans(n+1);
        for(int i=1;i<=n;i++){
            ans[i] = ans[i>>1] + (i&1);
        }
        return ans;
    }
};

Time Complexity: O(n)

Space Complexity: O(n)