Find the Maximum Repeating Number in Array  

Difficulty Level Easy
Frequently asked in Adobe Amazon Apple Bloomberg Citadel eBay Facebook Goldman Sachs Google Intuit Microsoft Nutanix PayPal Salesforce VMware Wish Yahoo
Array Zynga

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.

Please click Like if you loved this article?

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.

See also
Count Subsets Having Distinct Even Numbers

Space Complexity

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

Please click Like if you loved this article?