Number of bits for ** n** will be number of common bits in

**and**

*n***plus 1 (as diff between numbers is 1)**

*n-1*for example 3(0 1 1) and 4(1 0 0) have 0 common bits (0 0 0) this is number 0 so for 4 will be 0+1 bit

next, 4(1 0 0) and 5 (1 0 1) have 1 common bit (1 0 0) this is 4

and we already have number of bits calculated for number 4 in the array, so for 5 will be 1 + 1 bits

```
public int[] countBits(int num) {
int[] bits = new int[num+1];
for(int i = 1; i<= num; i++){
bits[i]=bits[i-1 & i] + 1;
}
return bits;
}
```