King Of Interviews

Counting Bits: 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.

Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Example 2:

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

Constraints:

0 <= n <= 10^5

Try this Problem on your own or check similar problems:

Number of 1 Bits

Solution:

public int[] countBits(int n) {
    int[] result = new int[n+1];
    result[0] = 0;

    for(int i = 1; i <= n; ++i){
        result[i] = result[i / 2] + i % 2;
    }

    return result;
}

Time/Space Complexity:

Time Complexity: O(n)
Space Complexity: O(1)

Explanation:

A Brute-force is to loop over range 0..n and transform each number into binary representation (only counting 1’s by determining modulo and the halving, in this case halving until we reach 0) and time complexity would be O(nlogn). You would probably be asked if you could optimize the solution. It’s a bit tricky to arrive at the final solution presented above and you can say it’s a DP problem with a twist. But anytime there is some calculation for a range included thing if you could optimize it by finding recurrence relations between numbers. In this case it’s obvious that we would need to halve the number to find the number of 1's appearing, but what if we have number of 1's for x/2 already calculated? We can use it to calculate the number of 1's for the current number using a bottom-up approach (using the previous smaller numbers to calculate larger numbers down the line). The only difference is if the current value is odd or even (always good to check the nature of the current value we’re trying to put into the formula, since it can allow us to make decisions). If the value is odd it means it has one more 1's than its halved pair, if it’s even that means it has the same 1's as its halved counter pair (e.g. 4=100, 8=1000 we are only shifting it to the left the total number of 1's stays the same).

Counting Bits