Leetcode: 338. Counting Bits

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Example:
For num = 5 you should return [0,1,1,2,1,2].

Follow up:

• 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?
• Space complexity should be O(n).
• Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

Hint:

1. You should make use of what you have produced already.
2. Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous.
3. Or does the odd/even status of the number help you in calculating the number of 1s?

Solution considering odd/even status of the number:
In this solution, we can think about if the number if even or odd. If the number is even, the number of 1s equal to the number which is half of it. For e.g., the number 8 has the same 1s as the number 4. The number 10 has the same amount of 1 bits as number 5. That is because number i is just left shift by 1 bit from number i / 2. Therefore, they should have the same number of 1 bits. 

For the number as odd, e.g. 1, 3, 5, 7. The number of 1 bits is equal to the number (i - 1) plus 1. For e.g., for number 3, the number of 1 bits equals to the number 2 plus 1. For number 11, it equals to number 10 + 1. 

Code (Java):

public class Solution {
    public int[] countBits(int num) {
        if (num < 0) {
            return new int[0];
        }
        
        int[] result = new int[num + 1];
        
        for (int i = 1; i <= num; i++) {
            if ((i & 1) == 0) {
                result[i] = result[i / 2];
            } else {
                result[i] = result[i - 1] + 1;
            }
        }
        
        return result;
    }
}

Update on 6/1/18:

class Solution {
    public int[] countBits(int num) {
        int[] dp = new int[num + 1];
        
        for (int i = 1; i < dp.length; i++) {
            dp[i] = dp[i & (i - 1)] + 1;
        }
        
        return dp;
    }
}