Find the maximum repeating number in O(n) time and O(1) extra space

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

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

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

  /**
     * 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.
     *
     * @param arr
     * @param k
     * @return
     */

    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;
    }