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!!