## 338. Counting Bits

Given a non negative integer number **num**. For every numbers **i** in the range **0 ≤ i ≤ num** calculate the number of 1's in their binary representation and return them as an array.

**Example 1:**

Input:2Output:[0,1,1]

**Example 2:**

Input:5Output:`[0,1,1,2,1,2]`

**Follow up:**

- It is very easy to come up with a solution with run time
**O(n*sizeof(integer))**. But can you do it in linear time**O(n)**/possibly in a single pass? - Space complexity should be
**O(n)**. - Can you do it like a boss? Do it without using any builtin function like
**__builtin_popcount**in c++ or in any other language.

## Rust Solution

```
struct Solution;
impl Solution {
fn count_bits(num: i32) -> Vec<i32> {
let n = num as usize;
let mut res = vec![];
for i in 0..=n {
res.push(i.count_ones() as i32);
}
res
}
}
#[test]
fn test() {
let num = 2;
let res = vec![0, 1, 1];
assert_eq!(Solution::count_bits(num), res);
}
```

Having problems with this solution? Click here to submit an issue on github.