Counting Bits

LeetCode Q 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 1: Input: 2 ; Output: [0,1,1]
Example 2: Input: 5 ; Output: [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.

Solution :

First, we try some examples to find the pattern.
| | binary | dp | |-----|--------|------| | 1 | 0001 | 1 | | 2 | 0010 | 1 | | 3 | 0011 | 2 | | 4 | 0100 | 1 | | 5 | 0101 | 2 | | 6 | 0110 | 2 | | 7 | 0111 | 3 | | 8 | 1000 | 1 | | 9 | 1001 | 2 | | 10 | 1010 | 2 | | 11 | 1011 | 3 | | 12 | 1100 | 2 |

We can find

1. When the number is power of 2, i.e. (1, 2, 4, 8,…) then there is only one 1 in its binary representation.
2. A target can be divided into two numbers. One is the largeset number which is the power of 2 and at the same time less than target.
   For example, 3 = 2 + 1; 10 = 8 + 2; 11 = 8 + 3.
   The number of 1s in this target is the sum of the number of 1s in these two sub-numbers. Since one sum-number is power of 2, the number of 1s in it is 1. Then, we can get the state transfer function as follows
   dp[i] = dp[i - num] + 1, where num is the largeset number which is the power of 2 and at the same time less than target.
   For example, 11 = 3 + 8, dp[11] = dp[3] + 1;

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

Code:

public int[] countBits(int num) {
	int[] dp = new int[num + 1];
	dp[0] = 0; int pow = 1
	for (int i = 1, t = 0; i <= num; i++, t++) {
		if (i == pow) { // update that largest power of 2 
			pow * = 2;
			t = 0;
		}
		dp[i] = dp[t] + 1;
	}
	return dp[num];
}