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

Leave a Comment

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

Wait !!! You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup