338.counting bits

Problem Statement:

• 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.

Approach

1. We could use previous solution as in 191.number-of-1-bits which calculates in O(logN) time and call it n times to get final solution in nlogn time.
2. do a DP solution
   • for every even number, the number of 1 bits are exactly equal to that of it's parent in a tree,
     • for example the 1 bits in number 4(100) are equal to bits in number 2(10) and so on
   • for every odd number, the number of 1 bits are +1 of its parent
     • for example the 1 bits in 21(10101) are exactly equal to 10(1010) + 1

###### Code:

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ans = {0};

        for(int i = 1; i <= n; i++){
            ans.push_back(ans[i/2]);
            if(i%2)
                ans[i] += 1;
        }
        return ans;
    }
};