Table of Contents
In the given unsorted array of size N. Given array contains numbers in range {0, k} where k <= N. Find the maximum repeating number.
That is the number which is coming large/maximum number of times in the array.
Example:
a) Input array is: [2, 3, 3, 4, 4, 5, 5, 3, 3, 6, 7, 8, 3]
Output: 3,
3 is coming 5 times maximum than any number in the given array.
b) Input array is: [2, 5, 4, 3, 2]
Output: 2,
2 is coming 2 times maximum than any number in the given array.
Algorithm
Time complexity: O(n)
Space complexity: O(1)
a. Iterate through the given array such that, for every element in the array.
array[array[i]%n] = array[array[i]%n] + n
b. After completing iterating in the array, find the index of the maximum element in the array.
c. The index is the maximum repeating element.
d. To get the original array back, do it for all elements,
array[i] = array[i]%k
Algorithm working
C++ Program
#include <iostream> #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; } //Main function int main() { int input_array[] = {3, 3, 4, 4, 5, 5, 2, 3, 6, 7, 8, 3}; int n = sizeof(input_array)/sizeof(int); cout<<"Maximum repeating element is: "<<MaxRepertingElement(input_array, n)<<endl; return 0; }