### Problem

In a provided vector `vec`

we need to find the majority element, if it is present. The *majority element* is the element that appears in the vector more than `n / 2`

times, where `n`

is a size of the vector `vec`

.

#### Example 1:

*Input:* `vec = [4, 8, 7, 4, 4, 5, 4, 3, 1, 4, 4]`

*Output:* `4`

*Explanation*: The majority element is `4`

because it appears in the vector `6`

times (more than `n / 2 = 11 / 2 = 5`

).

#### Example 2:

*Input:* `vec = [4, 8, 7, 4, 4, 5, 4, 3, 1, 4]`

*Output:* `None`

*Explanation*: There is no the majority element in the vector. Even though `4`

is the most common element, it is not the majority element, because it appears only `5`

times (not more than `n / 2 = 10 / 2 = 5`

times).

#### Example 3:

*Input:* `vec = [1]`

*Output:* `1`

#### Example 4:

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

*Output:* `None`

### Solution

```
fn find_majority_element(vec: &Vec<i32>) -> Option<i32> {
let mut m = 0;
let mut i = 0;
//first pass:
vec.iter().for_each(|&x| {
if i == 0 {
m = x;
i = 1;
} else if m == x {
i = i + 1;
} else {
i = i - 1;
}
});
//second pass:
let count = vec
.iter()
.fold(0, |count, &x| if x == m { count + 1 } else { count });
//return Some(m) if actual majority, None otherwise:
(count > vec.len() / 2).then(|| m)
}
```

### Explanation

The solution for this problem uses Boyer–Moore majority vote algorithm:

```
Initialize an element m and a counter i with i = 0
For each element x of the input sequence:
If i = 0, then assign m = x and i = 1
else if m = x, then assign i = i + 1
else assign i = i − 1
Return m
```

Also we need the second pass over the vector `vec`

because, even when there is no the majority element, the algorithm would yield one of the elements as the result (`m`

). On the second pass, we calculate a number of times (`count`

) we encounter `m`

element to check if that is the actual majority (it appears more than `vec.len() / 2`

times). If that is the case - we found the majority element. If not - we return `None`

.

### Complexity

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

(`n`

is a size of the input vector), but we need to iterate over the input vector twice. The auxiliary space complexity is constant (`O(1)`

).