follow up of leetcode 338, counting bits

// AMAN JAIN MCA 1st YEAR 2nd SEM

// time O(N), space O(N)
// Approach: Basic right shifting combined with DP
class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> dp;
        dp.push_back(0);
        if(n == 0) return dp;
        dp.push_back(1);
        if(n == 1) return dp;

        int i = 1;
        while(++i <= n) {
            if(i % 2 == 0) dp.push_back(dp[i/2]);
            else dp.push_back(1 + dp[i/2]);
        }
        return dp;
    }
};