## Problem:

Given an integer , find the number of 1 bits for every number (in binary form) starting from 0 to that integer.

## Input:

8

## Output:

[0,1,1,2,1,2,2,3,1]

For the number 8 , you need to find the number of 1 bits in the numbers 0,1,2,3,4,5,6,7,8 and store them in an output array in their respective index.

Try out the solution here:

https://leetcode.com/problems/counting-bits/

## Solution:

The below post explains how to find the number of 1 bits in a single integer :

The time complexity for the above algorithm(the optimal one) is O(**logn**).

If you use the above algorithm for each number upto the given integer input n , then it will take O(**nlogn**) time .

A better solution exists which takes only O(n) time complexity.

## Hint:

- When you divide a number by 2, it gets right shifted by 1 place and you loose the rightmost bit

## Optimal Solution:

Let’s analyze the above hint:

If you divide a number by 2, it gets right shifted by 1 digit.

So if it is an even number , the last digit will be 0 , so the number of “1 bits” remain the same even after the division.

So ,

Number of 1 bits in a even number = Number of 1 bits in the even number divided by 2.

If it is an odd number , the last digit will be 1 , so on right shifting (dividing by 2) you loose the last “1 bit”. Hence the number of 1 bits in an odd number is one less than the number of 1 bits in an odd number divided by 2.

So,

Number of 1 bits in a odd number = Number of 1 bits in the odd number divided by 2 + 1.

Using these two concepts , you can write an algorithm which finds the solution in a single pass (O(n) time).

Here is the algorithm:

## ALGORITHM:

**STEP1:** Initialize the first element of the output array to 0 (as the number of 1 bits in the element 0 is 0)

**STEP2:** For each element i from number 1 to the given integer n , find the number of 1 bits using the formula:

output[i] = output[i/2] for even numbers

output[i] = output[i/2] + 1 for odd numbers.

This can be represented in a single formula using :

output[i] = output[i/2] + (i%2)

i%2 will return 0 for even numbers and 1 for odd numbers.

**STEP3:** Return the output

## Code:

```
class Solution {
public int[] countBits(int n) {
int[] output = new int[n+1];
output[0] = 0;
for(int i =1;i<=n;i++){
output[i]=output[i/2]+i%2;
}
return output;
}
}
```

The time complexity of above code is O(n) since we iterate through the for loop upto n times.

Space complexity is O(n) for the output array.