Find the duplicate element most number of times in array of 0 to n-1

Problem

Given an array of n numbers from 0 to n-1, find the element occurring most number of times

Solution

This problem is similar to following problem :

• Find the two repeating elements in a given array

We can use some of the method used there.

Method 1 - Brute force
Here we will match the adjacent elements, and increment the count accordingly. Here is the code

public int maxDuplicateItemBruteForce(int[] A){
 int n = A.length;
 int counter = 0, max = 0, element = -1;
 for(int i = 0; i < A.length;i++){
  counter = 0;
  for(int j = 0; j<n;j++){
   if(A[i]==A[j])
    counter++;
  }
  if(counter > max) {
   max = counter;
   element = a[i];
  }
 }
 return element;
}

Method 2 - hashing or count array
We can borrow the method 2 of hashing from here.
Time complexity - O(n)
Space complexity - O(n)

Method 3 - Counting sort or normal sort
Time complexity - O(n log n) for comparison based sort and O(n) for counting sort.

Method 4
Method 5 and 6 of XORing and negation, mentioned here, will not work, but following is the O(n) time and O(1) extra space approach.

Let understand by example.
Let us understand the approach with a simple example where arr[] = {2, 3, 3, 5, 3, 4, 1, 7}, k = 8, n = 8 (number of elements in arr[]).
1) Iterate though input array arr[], for every element arr[i], increment arr[arr[i]%k] by k (arr[] becomes {2, 11, 11, 29, 11, 12, 1, 15 })
2) Find the maximum value in the modified array (maximum value is 29). Index of the maximum value is the maximum repeating element (index of 29 is 3).
3) If we want to get the original array back, we can iterate through the array one more time and do arr[i] = arr[i] % k where i varies from 0 to n-1.

Code in java(or cpp)

public int maxDuplicate(int[] A){
 int n = A.length;
 int max = 0, maxIndex;
 for(int i = 0; i < n;i++){
  A[A[i]%n] += n;
  
 for(int i = 0; i<n;i++){
  if(A[i]/n > max){
   max = A[i]/n;
   maxIndex = i;
  }   
 }
 return maxIndex;
}

What if we used (A[i] > n), instead of (A[i]/n > N)
Note that if we replace the condition , A[i]/n > max with A[i] > n, the above solution prints only one repeating element and doesn’t work if we want to print all maximum repeating elements. For example, if the input array is {2, 3, 2, 3}, the above solution will print only 3. What if we need to print both of 2 and 3 as both of them occur maximum number of times. Write a O(n) time and O(1) extra space function that prints all maximum repeating elements. (Hint: We can use maximum quotient arr[i]/n instead of maximum value in step 2).

Note that the above solutions may cause overflow if adding k repeatedly makes the value more than INT_MAX.

References
http://www.geeksforgeeks.org/find-the-maximum-repeating-number-in-ok-time/