# Program to find Maximum Repeating Element of Array in O(n) Time

• Write a program to find an element occurring maximum number of times in an array.
• How to find maximum repeating element of an array in O(n) time and without using any extra memory space.

Given an integer array of size N, containing elements from 0 to K where k < N. We have to find maximum repeating number in array in O(n) time complexity and O(1) space complexity.

```Input Array : [2, 4, 1 ,5, 6, 2, 4, 5, 4, 4]
Maximum Repeating Element : 4
Count : 4
```

Let inputArray be an integer array of size N containing elements from 0 to k(0< k By counting frequency of every element
Algorithm to find maximum repeating element of array by counting occurrence of every element
• We will use two loops to count the frequency of every array element. Outer loop will fix an element and inner loop will traverse the array and count it's occurrence.
• Keep track of the maximum count element found till now and compare it with count of current element.
Time Complexity : O(n2)
Space Complexity : O(1)

## C program to find maximum repeating number in O(n2)

```#include<stdio.h>
#include<limits.h>

/* This function prints the maximum occuring element of array */
void getMaxCountElement(int *array, int size) {
int i, j, maxCount, maxElement, count;
maxCount = INT_MIN;
/* Count the frequency of every elemenet of array,
and check if it is greater than maximum count element
we found till now and update it accordingly  */
for(i = 0; i< size; i++){
count = 1;
for(j = i+1; j < size; j++){
if(array[j] == array[i]){
count++;
/* If count of current element is more than
maxCount, uodate maxCount and maxElement */
if(count > maxCount){
maxCount = count;
maxElement = array[j];
}
}
}
}
printf("Maximum Repeating Element : %d\nCount : %d",
maxElement, maxCount);
}

int main() {
int array = {2, 4, 1 ,5, 6, 2, 4, 5, 4, 4};

getMaxCountElement(array, 10);

return 0;
}
```
Output
```Maximum Repeating Element : 4
Count : 4
```

By using inputArray to store count of elements.
The core logic behind this algorithm is as follows:
• The range of element in inputArray is always less than size of size of inputArray(k < N).
• The count of the element inputArray[i] is stored at index inputArray[i]. For example count of 8 is stored at index 8.
• Traverse inputArray and for every element inputArray[i], increment inputArray[inputArray[i]%K] by K.
• inputArray[i]/K gives the count of i in inputArray.
• Keep track of the maximum count element found till now and compare it with count of current element.
Time Complexity : O(n)
Space Complexity : O(1)

## C program to find maximum occurring element in O(n) time and O(1) space

```#include<stdio.h>
#include<limits.h>

/* This function prints the maximum occuring element of array */
int getMaxCountElement(int *array, int size, int K) {
int i, max, maxElementIndex;
/* For every element array[i], increment
array[array[i]%K] by K*/
for(i = 0; i < size; i++) {
array[array[i]%K] += K;
}

/* Traverse array and find maximum count element */
max = array; maxElementIndex = 0;
for (i = 1; i < size; i++) {
if (array[i]/K > max) {
max = array[i]/K;
maxElementIndex = i;
}
}

return maxElementIndex;
}

int main() {
int array = {2, 3, 3, 5, 3, 4, 1, 7};

printf("Max Repeating Element is %d\n", getMaxCountElement(array, 8, 8));

return 0;
}
```
Output
```Max Repeating Element is 3
```