0
$\begingroup$

I came across a problem where i have list $arr[]$ of $M$ integers. I have to find all integers K (given there is at least 1 K)such that :

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

Now in one of the solutions given, the algo was

1. p = abs(arr[0]-arr[1]);
2. Find all divisors of p
3. All the values of K must be among one of the divisors of p

I am not able to understand why the value of $K$ must be within one of the divisors of $p$.

$\endgroup$

1 Answer 1

1
$\begingroup$

If $$a_1 \bmod K = a_2 \bmod K$$ then $(a_1 - a_2) \bmod K = 0$, which means that $a_1 - a_2$ is a multiple of $K$, i.e. $K$ is a divisor of $a_1 - a_2$.

Or more explicitly:

$$ a_1 = k_1 K + l_1 \\ a_2 = k_2 K + l_2 $$ implies $$ p = |a_1 - a_2| = |k_1 - k_2| \, K $$

Of course, for each divisor of $K$ of $p$, you still have to check if $a_j \bmod K = a_1 \bmod K$ holds for $j = 3, \ldots, M$. (Equivalently: $a_j - a_1$ is divisible by $K$ for $j = 3, \ldots, M$.)

So the proposed algorithm is just a method to find a set of candidates for possible solutions $K$.

$\endgroup$
4
  • $\begingroup$ Okay @Martin. But why only divisors of arr[0]-arr[1] is calculated? The value of K can also be among the divisors of arr[2]-arr[1],arr[3]-arr[2] and so on? $\endgroup$
    – Diffy
    Commented Nov 28, 2015 at 11:31
  • $\begingroup$ @Diffy: That is correct. $K$ is a divisor of all (non-zero) differences $a_i - a_j$. The proposed algorithm is just one possible method. You could choose any of the differences and compute their divisors as candidates for $K$. $\endgroup$
    – Martin R
    Commented Nov 28, 2015 at 11:32
  • $\begingroup$ what i am asking is if i have to find every K, then shouldnt i take all possible pairs like p1=arr[2]-arr[1],p2=arr[3]-arr[2] etc. and then K can be among the divisors of p1,p2 etc? Is checking for only 1 pair(p[1]-p[0]) if enough? $\endgroup$
    – Diffy
    Commented Nov 28, 2015 at 11:37
  • $\begingroup$ @Diffy: See updated answer. $\endgroup$
    – Martin R
    Commented Nov 28, 2015 at 11:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .