Find the Maximum Repeating Number in Array

Problem Statement

In the “Find the Maximum Repeating Number in Array” problem we have given an unsorted array of size N. Given array contains numbers in range {0, k} where k <= N. Find the number that is coming the maximum number of times in the array.

Input Format

The first and only one line containing an integer n.

Second-line containing n space-separated integer denoting the input array.

Output Format

The first and only one line containing an integer denoting the number which is coming maximum number of times in the array.

Constraints

• 1<=n<=10^6
• 1<=a[i]<=n

Example

13
2 3 3 4 4 5 5 3 3 6 7 8 3

3

Explanation: 3 is coming 5 times maximum than any number in the given array.

5
2 5 4 3 2

2

Explanation: 2 is coming 2 times maximum than any number in the given array.

Algorithm

•  Iterate through the given array element by element.
• For every element in the array we do array[array[i]%n] = array[array[i]%n] + n.
• After completing iterating in the array, find the index of the maximum element in the array.
• The index is the maximum repeating element.
• To get the original array back, do it for all elements, array[i] = array[i]%k

Implementation

C++ Program to Find the Maximum Repeating Number in Array

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

int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    cout<<MaxRepertingElement(a, n)<<endl;
    return 0;
}

Java Program to Find the Maximum Repeating Number in Array

import java.util.Scanner;
class sum
{
    //Rearrange function  
    public static int MaxRepertingElement(int array[], int n)
    {
      //modify the array 
      for (int i = 0; i< n; i++)
      {
        array[array[i]%n] += n;
      }
      int max_element = -1,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;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int ans = MaxRepertingElement(a, n);
        System.out.println(ans);
    }
}

5
1 1 1 2 3

1

Complexity Analysis

Time Complexity

O(n) where n is the size of the given array. Here we simply traverse the whole array and perform the operation in constant time for every position.

Space Complexity

O(1) because we don’t use any auxiliary space here.