Home » Technical Interview Questions » Array Interview Questions » Find the maximum repeating number in array

Find the maximum repeating number in array


Reading Time - 0 mins

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;
}

READ  Leetcode Permutations
Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions