## Counting Bits In a Number – Leetcode

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`

## Solution

This is a standard approach where we keep dividing the number by 2 until it becomes zero and count the once in remainder e.g.

RECURSIVE SOLUTION –

```class Solution {
public int[] countBits(int n) {
int bits[] = new int[n+1];
for(int i = 0; i <= n; i++)
bits[i] = getBits(i);
return bits;
}

public int getBits(int n) {
if(n == 0)
return 0;
return (n%2 == 0 ? 0 : 1) + getBits(n/2);
}
}
```

DYNAMIC SOLUTION – We can optimise this code by avoiding repetive calculation.

```class Solution {
public int[] countBits(int n) {
int bits[] = new int[n+1];
for(int i = 0; i <= n; i++)
bits[i] = getBits(i, bits);
return bits;
}

public int getBits(int n, int[] bits) {
if(n == 0)
return 0;
if(bits[n] > 0) return bits[n];
return (n%2 == 0 ? 0 : 1) + getBits(n/2, bits);
}
}
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.