Maximum repeating number

Given an array of integers, find the maximum repeating number in the array. Expected time complexity is O(n) and O(1) extra space.

Algorithm:
Let us understand the approach with a simple example where arr[] = {2,1, 3, 3,4, 3, 4, 1,3}, k = 5, n = 9 (number of elements in arr[]).

1) For every element arr[i], increment arr[arr[i]%k] by k (arr[] becomes {2, 11, 8, 23, 14, 3, 4,1,3})

2) Find the maximum value in the modified array (maximum value is 23). Index of the maximum value is the maximum repeating element (index of 23 is 3).

3) If we want to get the original array back, we can iterate through the array one more time and do arr[i] = arr[i] % k where i varies from 0 to n-1.

Implementation:

#include<iostream>

using namespace std;

int maxRepeating(int* arr, int n, int k)

{    

    for (int i = 0; i< n; i++)

        arr[arr[i]%k] += k;

    // Find index of the maximum repeating element

    int max = arr[0];

    int result = 0;

    for (int i = 1; i < n; i++)

    {

        if (arr[i] > max)

        {

            max = arr[i];

            result = i;

        }

    }

    //get the original array back

    for (int i = 0; i< n; i++)

       arr[i] = arr[i]%k;

     

    return result;

}

int main()

{

    int arr[] = {2, 1, 3, 3, 4, 3, 4, 1,3};

    int n = sizeof(arr)/sizeof(arr[0]);

    int k = 5;

    cout << "The maximum repeating number is " <<

         maxRepeating(arr, n, k) << endl;

    return 0;

}

Output:

The maximum repeating number is 3