 # Moore's Voting Algorithm: A Step-by-Step Guide to Finding the Majority Element

## Given an array of N integers return an element that occurs more than N/2 times in the given array.

### The Brute Force

The most Navie and brute force approach is -

1. Loop through each of the elements of the array

2. For each of the elements, find its count

3. If the count is `> N/2`, return it, breaking out of the loop

``````#include<iostream>
using namespace std;

int main() {
int arr[] = {2, 2, 1, 1, 1, 2, 2};
int N = 7;
int ans = -1;

for (int i = 0; i < N; i++) {
int elem = arr[i];
int count = 0;

for (int j = 0; j < N; j++) {
if (arr[j] == elem) {
count++;
}
}

if (count > N / 2) {
ans = arr[i];
break;
}
}

cout << ans << endl;
}
``````

The time complexity for the brute force approach comes out to be O(N^2).

### The Better

The better approach involves using an auxiliary space in which we can save the frequency of each element. Whoever has a frequency greater than or equal to N/2 will be returned. We can use any data structure to store the element and its frequency, but we will be using maps.

The basic idea is -

1. Loop through the array and store the data in the map as an `element: frequency`.

2. Loop through the map and the first element that has a frequency greater than N/2 will be returned as the answer.

``````#include<iostream>
#include<map>
using namespace std;

int main() {
int arr[] = {2, 2, 1, 1, 1, 2, 2};
int N = 7;
int ans = -1;
map <int, int> mp;

for (int i = 0; i < N; i++) {
mp[arr[i]]++;
}

for (auto c: mp) {
if (c.second > N / 2) {
ans = c.first;
break;
}
}

cout << ans << endl;
}
``````

The time complexity for the better approach comes out to be O(N + NLogN), but it will have a space complexity of O(N) because of the maps that we used.

### The Optimal

We can write the most optimized code by using Moore's Voting Algorithm. Let's understand what it is -

Let's take two variables - `el`, `count`

The basic idea behind the algorithm is to identify the majority element, which is the element that appears more than N/2 times in the array. All the elements that are not the majority element will get canceled out, leaving only the majority element.

To find the majority element, we assume an element to be the majority element and traverse the array. If we encounter the same element, we increase the `count` variable, indicating that the element is a potential majority element. If we encounter a different element, we decrease the `count`, signifying that the current elements are getting canceled out.

If the `count` becomes 0, it means that the current elements are canceled out, and we assume a new element as the potential majority element and continue the process.

``````#include<iostream>
using namespace std;

int main() {
int arr[] = {2, 2, 1, 1, 1, 2, 2};
int N = 7;
int el;
int count = 0;

for (int i = 0; i < N; i++) {
if (count == 0) {
count = 1;
el = arr[i];
} else if (el == arr[i]) {
count++;
} else {
count--;
}
}

cout << el << endl;
}
``````

Now, If we look at each iteration of the above example -

1. 1st Iteration: the `count` is 0, and we assume 2 as the majority element by setting it to `el`. The `count` is then increased by 1.

2. 2nd Iteration: since the value of `arr[i]` is equal to `el`, we increment the `count` to 1, indicating that 2 is a potential majority element.

3. 3rd Iteration: `arr[i]` is 1, so we decrease the `count` by 1, signifying that the current elements are getting canceled out.

4. 4th Iteration: `arr[i]` is again 1 and since the `count` is greater than 1, we decrease it to 0, indicating that the assumed majority element (2) is not the actual majority element.

5. 5th Iteration: the `count` is 0, so we assume 1 is the majority element and increase the `count` by 1.

6. 6th Iteration: `arr[i]` is 2, and we decrease the `count` to 0, indicating that the assumed majority element (1) is not the actual majority element.

7. 7th Iteration: the `count` is 0, so we assume 2 as the majority element again and increase the `count` by 1.

After completing the for loop, `el` holds the actual majority element, which is 2. We can see that all elements apart from the last 2 were canceled out due to the same `count`, making 2 the majority element.

Now, this is the most optimal way of sorting the array it only takes, O(N) time.

We can also check if this is the majority element or not, simply by looping through the array -

``````#include<iostream>
using namespace std;

int main() {
int arr[] = {2, 2, 1, 1, 1, 2, 2};
int N = 7;
int count = 0;
int el = 2; // result of above code

for (int i = 0; i < N; i++) {
if (el == arr[i]) {
count++;
}
}

if (count > N / 2) {
cout << "YES " << el << " is the majority element" << endl;
} else {
cout << "NO " << el << " is not the majority element" << endl;
}
}
``````

Hope you had learned something from this.
Thanks for scrolling!!