# 338. Counting Bits(Solution || Leetcode easy || Java)

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 <= 105`

**Follow up:**

- It is very easy to come up with a solution with a runtime of
`O(n log n)`

. Can you do it in linear time`O(n)`

and possibly in a single pass? - Can you do it without using any built-in function (i.e., like
`__builtin_popcount`

in C++)?

# SOLUTION:

`class Solution {`

public int[] countBits(int n) {

//create an output array to return

int[] output = new int[n+1];

//start running the loop

for(int i = 1; i < output.length; i++){

//number of bits at i is equal to number of bits at

// i/2 and this i%2 is for the msb(most significant bit

//which tells us whether the number is odd or even)

output[i] = output[i/2] + i%2;

}

return output;

}

}

Runtime1 ms

Beats

99.98%

Memory46.4 MB

Beats

90.1%

Thank you for reading. If you have any queries then, please let me know in the comment section. I will surely be responsive toward it.