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

**approach.**

*O(n)*time and*O(1)*extra space*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/

## 0 comments:

## Post a Comment