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

&nbsp;
Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --&gt; 0
1 --&gt; 1
2 --&gt; 10


Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --&gt; 0
1 --&gt; 1
2 --&gt; 10
3 --&gt; 11
4 --&gt; 100
5 --&gt; 101


&nbsp;
Constraints:


	0 &lt;= n &lt;= 105


&nbsp;
Follow up:


	It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
	Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?


class Solution:
    def countBits(self, n: int) -> List[int]:
        # We know that all exponential values of two have 1 bit turned on, the rest are turned off.
        # Now, we can find a relation with following numbers after 2, where the numbers can be decomposed 
        # into smaller numbers where we already have found the # of 1s, for example.
        # F(3) = F(2^1) + F(1) = 1 + 1 = 3
        # F(4) = F(2^2) + F(0) = 1 + 0. ( Even thought we havent defined F(4) = F(2^2), by the previous established)
        # comment, we can safely say that all F(2^X) has only 1 bit so thats where F(4) would be = 1
        # F(5) = F(2^2) + F(1) = 1 + 1 = 2
        # F(6) = F(2^2) + F(2) = F(4) + F(2) = 1 + 1
        # The relation countinues for all following numbers
        
        # This solution is O(N)
        # With O(1) extra space ( considering dp is the returned answer )
        
        dp = [0]
		
        for i in range(1, n + 1):
            exponent = int(math.log(i) / math.log(2))
            num = 2**exponent
            decimal = i % (num)
            if num == i:
                dp.append(1)
            else:
                dp.append(dp[num] + dp[decimal])
        return(dp)
class Solution {

    public void count(int n, int[] a, int k)
    {
        int i;
        for(i=k ; i<k*2 && i<=n; i++)
            a[i]=a[i-k]+1;
        if(i==n+1)
            return;
        count(n,a,k*2);
    }
    public int[] countBits(int n) {
        int a[] = new int[n+1];
        a[0]=0;
        count(n,a,1);
        return a;
    }
}
class Solution {
private:
    int countones( int n ){
        int count = 0;
        while(n){
            count ++;
            n = n & ( n-1 );
        }
        return count;
    }
public:
    vector<int> countBits(int n) {
        vector<int> ans;
        for( int i = 0; i <= n; i++ ){
            int x = countones(i);
            ans.push_back(x);
        }
        return ans;
    }
};
var countBits = function(n) {
    if (n === 0) return [0];

    const ans = new Array(n + 1).fill(0);

    let currRoot = 0;
    for (let idx = 1; idx <= n; idx++) {
        if ((idx & (idx - 1)) === 0) {
            ans[idx] = 1;
            currRoot = idx;
            continue;
        }

        ans[idx] = 1 + ans[idx - currRoot];
    }

    return ans;
};
Counting Bits