# 338. Counting Bits

#### Easy

***

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

&#x20;

**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
```

&#x20;

**Constraints:**

* `0 <= n <= 10^5`

&#x20;

**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 1:

Using solution of [Problem 191: Number of 1 Bits](https://sumit-chaudhary.gitbook.io/leetcode-solutions/number-of-1-bits)

```python
class Solution:
    # O(nlogn)
    def countBits(self, n: int) -> List[int]:
        result = []
        for num in range(n+1):
            count = self.bit_count(num)
            result.append(count)
        return result
    
    def bit_count(self, n: int) -> int:
        count = 0
        while n != 0:
            count = count + (n&1)
            n = n >> 1
        return count
```

#### Solution 2:

Since multiplying by 2 just adds a zero, then any number and its double will have the same number of 1's. Likewise, doubling a number and adding one will increase the count by exactly 1. Or:

* `countBits(N) = countBits(2N)`
* `countBits(N)+1 = countBits(2N+1)`

Thus we can see that any number will have the same *bit count* as half that number, with an extra one if it's an odd number. We iterate through the range of numbers and calculate each bit count successively in this manner:

```python
for i in range(num):
    counter[i] = counter[i // 2] + i % 2
```

Complexity : O(n)

```python
class Solution:
    def countBits(self, n: int) -> List[int]:
        count = [0]
        for num in range(1, n+1):
            count.append(count[num >> 1] + num%2)
        return count
```