- 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

**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.

^{2})

Space Complexity : O(1)

## C program to find maximum repeating number in O(n^{2})

#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[10] = {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.

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[0]; 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[10] = {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