Given an array of size n, the array contains numbers in range from 0 to k-1 where k is a positive integer and k <= n. Find the maximum repeating number in this array. For example, let k be 10 the given array be arr[] = {1, 2, 2, 2, 0, 2, 0, 2, 3, 8, 0, 9, 2, 3}, the maximum repeating number would be 2. Expected time complexity is O(n) and extra space allowed is O(1). Modifications to array are allowed.
http://chengchao60827.blogspot.com/2013/03/find-maximum-repeating-number-in-on.html
The key of this question is how to prove, after first scan, the max element's index is the maximum repeating element.
Prove: Assume mi * k + ai > mj * k + aj && mj > mi && 0 <= ai < k && 0 <= aj < k.
So, ai - aj > (mj - mi) * k. (mi - mj) * k >= k. Therefore, ai - aj > k, which is impossible. so mi >= mj
public int findMostElement(int[] arr, int k) {
for (int i = 0; i < arr.length; i++) {
int value = arr[i] % k;
arr[value] += k;
}
int max = -1;
int mostElementIndex = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
mostElementIndex = i;
}
}
return mostElementIndex;
}
Read full article from Find the maximum repeating number in O(n) time and O(1) extra space | GeeksforGeeks
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.
How does the above algorithm work? Since we use arr[i]%k as index and add value k at the indexarr[i]%k, the index which is equal to maximum repeating element will have the maximum value in the end. Note that k is added maximum number of times at the index equal to maximum repeating element and all array elements are smaller than k.
int maxRepeating(int* arr, int n, int k){ // Iterate though input array, for every element // arr[i], increment arr[arr[i]%k] by k for (int i = 0; i< n; i++) arr[arr[i]%k] += k; // Find index of the maximum repeating element int max = arr[0], result = 0; for (int i = 1; i < n; i++) { if (arr[i] > max) { max = arr[i]; result = i; } } /* Uncomment this code to get the original array back for (int i = 0; i< n; i++) arr[i] = arr[i]%k; */ // Return index of the maximum element return result;}The key of this question is how to prove, after first scan, the max element's index is the maximum repeating element.
Prove: Assume mi * k + ai > mj * k + aj && mj > mi && 0 <= ai < k && 0 <= aj < k.
So, ai - aj > (mj - mi) * k. (mi - mj) * k >= k. Therefore, ai - aj > k, which is impossible. so mi >= mj
public int findMostElement(int[] arr, int k) {
for (int i = 0; i < arr.length; i++) {
int value = arr[i] % k;
arr[value] += k;
}
int max = -1;
int mostElementIndex = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
mostElementIndex = i;
}
}
return mostElementIndex;
}
Read full article from Find the maximum repeating number in O(n) time and O(1) extra space | GeeksforGeeks
