# 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 = 2Output: [0,1,1]Explanation:0 --> 01 --> 12 --> 10`

Example 2:

`Input: n = 5Output: [0,1,1,2,1,2]Explanation:0 --> 01 --> 12 --> 103 --> 114 --> 1005 --> 101`

Constraints:

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

--

--

## More from Palakkgoyal

Solutions to all your coding related problems at one point. DSA question on daily basis and much more.

## Get the Medium app

Solutions to all your coding related problems at one point. DSA question on daily basis and much more.