Find every K such that arr[i]%K is equal to for each arr[i]

algorithm, greatest-common-divisor, math, modular-arithmetic

Solution

First, let's examine the givens.

- Given that there exists at least one `K`, we know that, for example, the array `arr` such that `arr[0]=4; arr[1]=6; arr[2]=9` is not valid because no modulus gives the same result for each.

- Given that `K` > 1, we know that all values of the array cannot be the same. They are, however, the same `modK` for all `K`.

Keep in mind that `arr[i]%K` (for any i such that `0=<i<M`) does not have to be positive.

A Proposed Algorithm

Code has not been tested

It seems to me as if the simplest way of determining `K` values will be from finding the differences between each value in the array. (I'm going to show examples in Java.) Let's say that `arrDiff` contains the differences of each value such that

arrDiff[0] = arr[0]-arr[1];
arrDiff[1] = arr[1] - arr[2];
...
arrDiff[M-1] = arr[M-1] - arr[0];

Now, find `G = gcd(arrDiff[0],arrDiff[1],...,arrDiff[M-1]` to find all valid `K`. You can use whatever `gcd` method you wish, which is the Euclidean Algorithm, in order to iteratively/recursively find `G`. You can also ignore negative differences since `gcd` will give you positive results.

`[All of G's factors]>1` (including `G` itself) will be valid `K` values.

Walking Through It

I'm not going to do a proof (I'll leave that to you), but let's do an example just to be clear.

Initialize an example `arr`

//Let's do an easy one with M=3
int arr[] = new int[3];
arr[0] = -7;
arr[1] = 9;
arr[2] = 25

Create the difference array

I'll show a slightly more efficient implementation here (thanks to @RBarryYoung).

int min = findSmallestNumber(arr); //Returns min value (may be negative)
//The array size is intended to not include the minimum, assuming we have no duplicates.
int arrDiff[] = new int[arr.length-1];
for(int num : arr){
    if(num==min) continue; 
    arrDiff[num] = arr[num] - min;
}

For the example above, this code should give us values of `16,32` in `arrDiff`. Notice that using this method should result in all positive values for gcd calculations in the next step.

Calculate `G = gcd`

I'm not going to write a gcd method for you, since there are lots of implementations; I'll assume you have a method `int gcd(int a, int b)`.

int g = gcd(arrDiff[0], arrDiff[1]);
for(int i = 2, i < arrDiff.length-1, i++){
    g = gcd(g, arrDiff[i]);
}
//return g; 

Note that if we only have two values in the array, no `gcd` usage is necessary--just use the single difference.

Checking the Example

For our example, you can easily find that the gcd(-16,-16,32)=gcd(16,16,32)=16. Thus 16 and all of its factors >1 should be answers. Let's check 16 at least. Note that the below "=" should really be a congruence symbol (three bars not two).

-7mod16 = 9mod16

9mod16 = 9mod16

25mod16 = 9mod16

You can check that this also works for factors `2,4,8`. (For all of these factors, you should get `1mod8 => 1mod4 => 1mod2`.)

Wrap-up

If you have to find the factors in code, you may be interested in one of the various factoring algorithms to find all factors of `G` greater than 1. Picking the most optimized may depend on your data.

Thus, it's really a combination of algorithms which you may need. There may be slightly faster ways of doing what I showed you above, but the basic algorithm should be approachable now.

Problem

Original source