Problem: Write a C++ program to find the most repeated element in the given array. Most repeated element is that element which has occurred most in whole array.

Example:

``````Input:  {1, 2, 5, 3, 7, 3, 4, 2, 2, 6}
Output: 2

Input:  {1, 5, 8, 7, 7, 5, 3, 5, 5, 9}
Output: 7``````

There are several ways we can solve this problem. Let’s see two of the approaches with example.

## Method 1: Using Sorting [O(nlogn)]

In this approach, we sort the elements of the array in ascending order then count the frequency of the elements.

By sorting, the duplicates element comes together, which makes counting of the frequency of unique elements easier.

Here is the C++ code that finds the most repeated element using the sorting technique:

``````#include <iostream>
#include <algorithm>

int main() {
int arr[] = {2, 4, 6, 4, 2, 4, 5, 8};
int n = sizeof(arr) / sizeof(arr);

// sort the array
std::sort(arr, arr + n);

// initialize variables to keep track of current element and its frequency
int current_element = arr;
int current_count = 1;
int max_element = arr;
int max_count = 1;

// iterate through the array
for (int i = 1; i < n; i++) {
if (arr[i] == current_element) {
// if the current element is the same as the previous one, increment the count
current_count++;
} else {
// if the current element is different, check if it has a higher frequency than the previous max
if (current_count > max_count) {
max_element = current_element;
max_count = current_count;
}

// update the current element and its count
current_element = arr[i];
current_count = 1;
}
}
// check if the last element is the most frequent
if (current_count > max_count) {
max_element = current_element;
}
std::cout << "The most repeated element is: " << max_element << std::endl;
return 0;
}
``````

Output:

The most repeated element is: 4

Time Complexity: O(nlogn)
Space Complexity: O(1)

In this program, after the sorting the array using `std::sort()` function, we use two pointers to iterate through the array and keep track of the current element and its frequency to find the most frequent element.

This is not the efficient way of finding the most repeated element, as it involves sorting which increases the time complexity to O(nlogn). Let’s see another approach to solve this problem in O(n).

## Method 2: Using Map [O(n)]

In this method we use an `unordered_map` to store the count of each element in the input array.

For this, we iterate through the input array and update its frequency in the unordered map as `map[array[i]]++`.

Finally, we iterate through the map and keep track of the element with the highest count and output it.

``````#include <iostream>
#include <algorithm>
#include <unordered_map>

int main() {
int arr[] = {2, 4, 6, 4, 2, 4, 5, 8};
int n = sizeof(arr) / sizeof(arr);

// Create an unordered_map to store the frequency of each element
std::unordered_map<int, int> freq;
for (int i = 0; i < n; i++) {
freq[arr[i]]++;
}

// Initialize variables to keep track of the most frequent element
int max_element = 0;
int max_count = 0;

// Iterate through the map and update the max element and count
for (const auto& [element, count] : freq) {
if (count > max_count) {
max_element = element;
max_count = count;
}
}

std::cout << "The most repeated element is: " << max_element << std::endl;
return 0;
}
``````

Output:

The most repeated element is: 4

Time Complexity: O(n)
Space Complexity: O(n)

Because we have used an auxiliary unordered map to store the frequency of elements, the space complexity grows to O(n).

There are other various ways to find the most occurring element in the array. I have only shown you two of them.