# Find the Maximum Repeating Number in Array

Difficulty Level Easy
Array ZyngaViews 9157

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

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

Translate »