[LeetCode] Counting Bits

This problem is from  leetcode 

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].

Let's list the some examples, left column are the numbers, the right column are the number of bits for each number.

0 0
1 1 <-- go back to 1
2 1 <-- go back to 1
3 2
4 1 <-- go back to 1
5 2
6 2
7 3
8 1 <-- go back to 1
.
.
.
16 1 <-- go back to 1

First of all, we observe for every 2^n number, the number of bits will be 1. Now we need to figure out the number of bits for each number between the 2^(n-1) and 2^n. Using function bits(int num) as example, we can see
bits(2)=1
bits(3) = bits(2) + bits(3-2)
bits(4) = 1
bits(5) = bits(4) + bits(5-4)
bits(6) = bits(4) + bits(6-4)
bits(7) = bits(4) + bits(7-4)
bits(8) = 1

Got it?

 

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

view raw countBits.java hosted with ❤ by GitHub