How to find all possible K values for the given problem?



Given an array of N integers.

a[1]%K = a[2]%K = a[3]%K = … a[n]%K

  1. 1<K<N, 1< N<10^6, 1<a*<10^9

  2. How will you find all possible values for K?

P.S : No brute force approach.


Can you please give some Q link? People need it to verify that this isnt related to an on-going contest. I will be happy to help after that :slight_smile:


Hint: if a_1 ext{ mod } K = a_2 ext{ mod } K, then (a_1 - a_2) ext{ mod } K = 0. Therefore K has to be a divisor of a_1 - a_2.


It is not related to ongoing contest. Link


Thanks!! :slight_smile: