*1.9K*

Question:Given an array of n numbers. Give an algorithm for finding the element which appears maximum number of times in the array?Input: 3, 2, 1, 2, 2, 3

Output: 2

The previous method required us to sort the array. But what if we do not want to sort the array. We can also solve this problem using 2 scans of the array. We cannot use the negation method used to check duplicates because of the number of repetitions. In the first scan, instead of negating -> add the value n. That means for each of occurrence of an element add the array size to that element. In the second scan, check the element value by dividing it with n and return the element whichever gives the maximum value.

The algorithm can be coded as:-

int maxRepetitions(int arr[], int size) { int i = 0, max = 0, maxIndex; for(i=0;i<size;i++) arr[arr[i]%n] += n; for(i=0;i<n;i++) if(arr[i]/n > max) { max = arr[i]/n; maxIndex = i; } return arr[maxIndex]; }

Notes:

- This solution does not work if the array is read-only.
- The solution only works if the array elements are positive.
- If the elements range is not 0 to n-1 then it may give exceptions.

*Time Complexity:-* O(n) because no nested for loops are required.

*Space Complexity:-* O(1)