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.
I solved it in Java. 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
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
Note that the above solutions may cause
overflow if adding k repeatedly makes the value more than INT_MAX.
