Values with Equal Array Remainders

Problem Overview

A modulus k gives the same remainder for every array value exactly when k divides every pairwise difference.

Intuition

A modulus k gives the same remainder for every array value exactly when k divides every pairwise difference. Those differences are captured by the gcd of each value minus the minimum. Every positive divisor of that gcd is a valid k.

Algorithm

1Find the minimum value in the array.
2Compute g = gcd of all (arr[i] - min).
3If g is 0, every element is equal, so return -1.
4Count the positive divisors of g and return that count.

Example Walkthrough

Input: arr = [2, 4, 6]

1. min = 2, so differences are 0, 2, 4 and g = 2.
2. Divisors of 2 are 1 and 2.
3. Both leave remainder 0 for every element.

Output: 2

Common Pitfalls

• All equal elements mean infinitely many k; the problem asks for -1.
• Do not scan k up to max(arr); only divisors of g matter.
• g = 0 is the all-equal case, not a divisor to count.
• Use long when checking i * i <= g to avoid overflow.

Values with Equal Array Remainders.java

Java

// Approach: arr[i]%k equals for all i iff k divides every difference. Let
// g = gcd of (arr[i] - min). If g is 0 (all equal), return -1. Otherwise the
// answer is the number of positive divisors of g.
// Complexity: O(n + sqrt(g)) time and O(1) extra space.
class Solution {

    private int gcd(int a, int b) {
        while (b != 0) {
            int t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    public int sameMod(int[] arr) {
        int min = arr[0];
        for (int x : arr) {
            min = Math.min(min, x);
        }

        int g = 0;
        for (int x : arr) {
            g = gcd(g, x - min);
        }

        if (g == 0) {
            return -1;
        }

        int count = 0;
        for (int i = 1; (long) i * i <= g; i++) {
            if (g % i == 0) {
                count++;
                if (i != g / i) {
                    count++;
                }
            }
        }
        return count;
    }
}

Was this solution helpful?