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

general
, , , ,
1

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[i]<10^9

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

P.S : No brute force approach.

2

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:

3

It is not related to ongoing contest. Link

4

Thanks!! :slight_smile:

5

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

1 Like