# 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

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

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