> For the complete documentation index, see [llms.txt](https://docs-57.gitbook.io/data-structure-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs-57.gitbook.io/data-structure-and-algorithms/problems/bit-manipulation/binary-bits-count-ii.md).

# Binary Bits Count II

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

```csharp
public class Solution {
    public int[] CountBits(int n) {
        
        var result = new int[n+1];
        for(int i=0;i<=n;i++)
        {
            int num=i;
            int count = 0;
            while (num != 0) {
                 count += (int)(num & 1);
                 num >>= 1;
            }
            result[i]=count;
        }
        return result;
    }
}
```

The time complexity of the algorithm is **O(n log m)**, where `n` is the input to the function and `m` is the maximum number in the range from `0` to `n`. This is because there are `n` numbers in the range, and for each number, we’re counting the number of ‘1’ bits, which takes `log(m)` time in the worst case.

The space complexity of the algorithm is **O(n)**, which means it uses a linear amount of space. This is because we’re creating an array result of size `n+1` to store the bit counts for all numbers from `0` to `n`. The size of this array grows linearly with the size of the input.