Given anon negativeinteger number num. For every numbers i in the range0 ≤ i ≤ numcalculate the number of 1's in their binary representation and return them as an array.

Have you met this question in a real interview?

Yes

Example

Given num =5you should return[0,1,1,2,1,2].

Challenge

1. It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
2. Space complexity should be O(n).
3. Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

public class Solution {
    /**
     * @param num a non negative integer number
     * @return an array represent the number of 1's in their binary
     */

    //f[n] represents number of 1 in bits
    //f[n] = f[n >> 1] + n % 2
    //init f[0] = 0
    //from small to large
    public int[] countBits(int num) {
        // Write your code here
        int[] ans = new int[num + 1];
        int[] f = new int[num + 1];

        int i;
        for (i = 0; i <= num; i++) {
            f[i] = f[i >> 1] + i % 2;         
        }

        return f;
    }

}