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