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

Question

I have an array of M integers. I have to find all possible integers K (given there is at least 1 K)such that:

1) K > 1
2) arr[0]%K = arr[1]%K = arr[2]%K = ... = arr[M-1]%K 

What is the best algorithm for this problem?

Answer 1

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.