### Problem

We need to sort a provided binary vector `vec`

(a vector that contains only `0`

or `1`

numbers) in linear time.

#### Example 1:

*Input:* `vec = [1, 0, 1, 0, 1, 0, 0, 1]`

*Output:* `[0, 0, 0, 0, 1, 1, 1, 1]`

#### Example 2:

*Input:* `vec = [0, 0, 1, 0, 1, 1, 0, 1, 0, 0]`

*Output:* `[0, 0, 0, 0, 0, 0, 1, 1, 1, 1]`

#### Example 3:

*Input:* `vec = [0, 0, 1, 1]`

*Output:* `[0, 0, 1, 1]`

### Solution

```
fn sort_binary_vector_in_linear_time(vec: &mut Vec<u8>) -> &Vec<u8> {
let count_0 = vec.iter().fold(0, |acc, e| match e {
0 => acc + 1,
1 => acc,
_ => panic!("The vector is not binary"),
});
for i in 0..vec.len() {
if i < count_0 {
vec[i] = 0;
} else {
vec[i] = 1;
}
}
return vec;
}
```

### Explanation

Since we know that the vector `vec`

is a binary vector as per the requirement (could contain only values `0`

and `1`

), we could avoid using more general sorting algorithms. Instead, we could just count a number of `0`

elements (or alternatively a number of `1`

) using a simple `fold`

operation. And then we iterate once again over the vector `vec`

to fill elements with the index *below* that `count_0`

with `0`

, and the rest of the elements with `1`

.

### Complexity

The time complexity of this solution is `O(n)`

(`n`

is a size of the input vector).