Find the maximum repeating number in array

In the given unsorted array of size N. Given array contains numbers in range {0, k} where k <= N. Find the maximum repeating number.

That is the number which is coming large/maximum number of times in the array.

Example:

a) Input array is: [2, 3, 3, 4, 4, 5, 5, 3, 3, 6, 7, 8, 3]
Output: 3,
3 is coming 5 times maximum than any number in the given array.

b) Input array is: [2, 5, 4, 3, 2]
Output: 2,
2 is coming 2 times maximum than any number in the given array.

Algorithm

Time complexity: O(n)
Space complexity: O(1)

a. Iterate through the given array such that, for every element in the array.
array[array[i]%n] = array[array[i]%n] + n

b. After completing iterating in the array, find the index of the maximum element in the array.

c. The index is the maximum repeating element.

d. To get the original array back, do it for all elements,
array[i] = array[i]%k

Algorithm working

C++ Program

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int MaxRepertingElement(int* array, int n)
{
	//modify the array 
	for (int i = 0; i< n; i++)
	{
		array[array[i]%n] += n;
	}
	int max_element = INT_MIN,result = 0;
	for (int i = 0; i < n; i++)
	{
		if (array[i] > max_element)
		{
			max_element = array[i];
			result = i;
		}
	}
	//get the array back to original values
	for (int i = 0; i< n; i++)
	{
		array[i] = array[i]%n; 
	}
	return result;
}

//Main function
int main()
{
	int input_array[] = {3, 3, 4, 4, 5, 5, 2, 3, 6, 7, 8, 3};
	int n = sizeof(input_array)/sizeof(int);
	cout<<"Maximum repeating element is: "<<MaxRepertingElement(input_array, n)<<endl;
	return 0;
}