# 338. Counting Bits

> Nguồn: https://tiennhm.io.vn/docs/leetcode/bit-manipulation/338-counting-bits
> 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`.

## Giới thiệu bài toán

Chi tiết: https://leetcode.com/problems/counting-bits/

> **Tip: Yêu cầu**
>
> 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:
```log
0 --> 0
1 --> 1
2 --> 10
```

**Example 2:**

- Input: n = 5
- Output: [0,1,1,2,1,2]
- Explanation:
```log
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++)?

## Giải quyết bài toán

        {CountingBitsCs}

        {CountingBitsPy}

        {CountingBitsJs}

        {CountingBitsTs}

**Tham khảo:**
- [C#](https://leetcode.com/submissions/detail/1039509439/)
- [Python](https://leetcode.com/submissions/detail/1039538497/)
- [JavaScript](https://leetcode.com/submissions/detail/1039545417/)
- [TypeScript](https://leetcode.com/submissions/detail/1039547895/)