Question: Given an array of n numbers. Give an algorithm for finding the element which appears maximum number of times in the array?
Input: 3, 2, 1, 2, 2, 3
Output: 2
One simple and a brute force solution to this is, for each input element check whether there is any element with same value and for each occurrence, increment the counter. Each time, check the current counter with the max counter and update it if this value is greater than max counter. This we can solve just by using two simple for loops.
#include<stdio.h>
//to find the number with maximum duplicates in array
int maxDuplicatesBruteForce(int arr[], int size)
{
int counter = 0;
int max = 0;
int index_max = 0; //to store the index of maximum duplicated element
int i,j;
for(i=0;i<size;i++)
{
counter = 0;
for(j=0;j<size;j++)
{
//check for duplicates in the array
if(arr[i] == arr[j])
counter++;
}
//update the counter and max_index
if(counter > max)
{
max = counter;
index_max = i;
}
}
//return the maximum duplicated element
return arr[index_max];
}
int main(void)
{
int arr[] = {3, 2, 1, 2, 2, 3};
printf("Max duplicated = %d",maxDuplicatesBruteForce(arr, 6));
return 0;
}
Time Complexity:- O(n2)
Space Complexity:- O(1)