# Finding ‘k’ such that its modulus with each array element is same

Given an array of n integers .We need to find all ‘k’ such that

`arr % k = arr % k = ....... = arr[n-1] % k `

Examples:

```Input  : arr[] = {6, 38, 34}
Output : 1 2 4
6%1 = 38%1 = 34%1 = 0
6%2 = 38%2 = 34%2 = 0
6%4 = 38%4 = 34%2 = 2

Input  : arr[] = {3, 2}
Output : 1
```

Suppose the array contains only two elements a and b (b>a). So we can write b = a + d where d is a positive integer and ‘k’ be a number such that b%k = a%k.

```(a + d)%k = a%k
a%k + d%k = a%k
d%k = 0
```

Now what we get from the above calculation is that ‘k’ should be a divisor of difference between the two numbers.
Now what we have to do when we have an array of integers

1. Find out the difference ‘d’ between maximum and minimum element of the array
2. Find out all the divisors of ‘d’
3. Step 3: For each divisor check if arr[i]%divisor(d) is same or not .if it is same print it.

## C++

 `// C++ implementation of finding all k ` `// such that arr[i]%k is same for each i ` `#include ` `using` `namespace` `std; ` ` `  `// Prints all k such that arr[i]%k is same for all i ` `void` `printEqualModNumbers (``int` `arr[], ``int` `n) ` `{ ` `    ``// sort the numbers ` `    ``sort(arr, arr + n); ` ` `  `    ``// max difference will be the difference between ` `    ``// first and last element of sorted array ` `    ``int` `d = arr[n-1] - arr; ` ` `  `    ``// Find all divisors of d and store in ` `    ``// a vector v[] ` `    ``vector <``int``> v; ` `    ``for` `(``int` `i=1; i*i<=d; i++) ` `    ``{ ` `        ``if` `(d%i == 0) ` `        ``{ ` `            ``v.push_back(i); ` `            ``if` `(i != d/i) ` `                ``v.push_back(d/i); ` `        ``} ` `    ``} ` ` `  `    ``// check for each v[i] if its modulus with ` `    ``// each array element is same or not ` `    ``for` `(``int` `i=0; i

## Java

 `//  Java implementation of finding all k ` `// such that arr[i]%k is same for each i ` ` `  `import` `java.util.Arrays; ` `import` `java.util.Vector; ` ` `  `class` `Test ` `{ ` `    ``// Prints all k such that arr[i]%k is same for all i ` `    ``static` `void` `printEqualModNumbers (``int` `arr[], ``int` `n) ` `    ``{ ` `        ``// sort the numbers ` `        ``Arrays.sort(arr); ` `      `  `        ``// max difference will be the difference between ` `        ``// first and last element of sorted array ` `        ``int` `d = arr[n-``1``] - arr[``0``]; ` `      `  `        ``// Find all divisors of d and store in ` `        ``// a vector v[] ` `        ``Vector v = ``new` `Vector<>(); ` `        ``for` `(``int` `i=``1``; i*i<=d; i++) ` `        ``{ ` `            ``if` `(d%i == ``0``) ` `            ``{ ` `                ``v.add(i); ` `                ``if` `(i != d/i) ` `                    ``v.add(d/i); ` `            ``} ` `        ``} ` `      `  `        ``// check for each v[i] if its modulus with ` `        ``// each array element is same or not ` `        ``for` `(``int` `i=``0``; i

## Python3

 `# Python3 implementation of finding all k  ` `# such that arr[i]%k is same for each i  ` ` `  `# Prints all k such that arr[i]%k is  ` `# same for all i  ` `def` `printEqualModNumbers(arr, n): ` `     `  `    ``# sort the numbers  ` `    ``arr.sort();  ` `     `  `    ``# max difference will be the difference  ` `    ``# between first and last element of  ` `    ``# sorted array  ` `    ``d ``=` `arr[n ``-` `1``] ``-` `arr[``0``];  ` `     `  `    ``# Find all divisors of d and store  ` `    ``# in a vector v[]  ` `    ``v ``=` `[]; ` `    ``i ``=` `1``; ` `    ``while` `(i ``*` `i <``=` `d):  ` `        ``if` `(d ``%` `i ``=``=` `0``):  ` `                ``v.append(i); ` `                ``if` `(i !``=` `d ``/` `i): ` `                    ``v.append(d ``/` `i); ` `        ``i ``+``=` `1``; ` `     `  `    ``# check for each v[i] if its modulus with  ` `    ``# each array element is same or not  ` `    ``for` `i ``in` `range``(``len``(v)):  ` `        ``temp ``=` `arr[``0``] ``%` `v[i];  ` `     `  `        ``# checking for each array element if  ` `        ``# its modulus with k is equal to k or not  ` `        ``j ``=` `1``;  ` `        ``while` `(j < n):  ` `            ``if` `(arr[j] ``%` `v[i] !``=` `temp):  ` `                ``break``; ` `            ``j ``+``=` `1``; ` ` `  `        ``# if check is true print v[i]  ` `        ``if` `(j ``=``=` `n):  ` `            ``print``(v[i], end ``=` `" "``);  ` ` `  `# Driver Code ` `arr ``=` `[``38``, ``6``, ``34``];  ` `printEqualModNumbers(arr, ``len``(arr));  ` `         `  `# This code is contributed by mits `

## C#

 `// C# implementation of finding all k  ` `// such that arr[i]%k is same for each i  ` `using` `System; ` `using` `System.Collections; ` `class` `Test  ` `{  ` `    ``// Prints all k such that arr[i]%k is same for all i  ` `    ``static` `void` `printEqualModNumbers (``int` `[]arr, ``int` `n)  ` `    ``{  ` `        ``// sort the numbers  ` `        ``Array.Sort(arr);  ` `     `  `        ``// max difference will be the difference between  ` `        ``// first and last element of sorted array  ` `        ``int` `d = arr[n-1] - arr;  ` `     `  `        ``// Find all divisors of d and store in  ` `        ``// a vector v[]  ` `        ``ArrayList v = ``new` `ArrayList();  ` `        ``for` `(``int` `i=1; i*i<=d; i++)  ` `        ``{  ` `            ``if` `(d%i == 0)  ` `            ``{  ` `                ``v.Add(i);  ` `                ``if` `(i != d/i)  ` `                    ``v.Add(d/i);  ` `            ``}  ` `        ``}  ` `     `  `        ``// check for each v[i] if its modulus with  ` `        ``// each array element is same or not  ` `        ``for` `(``int` `i=0; i

## PHP

 ` `

Output:

```1 2 4
```