Problem
Given an array of numbers, find the largest number $d$ such that, when elements of the array are divided by $d$, they leave the same remainder
Solution
We will be using our knowledge about
Congruence Relation and
GCD to solve this problem. But first, we need to make sure that we understand the problem properly.
Wrong Approach
At first, one might think that $d$ is the $gcd$ of array elements. Surely, dividing elements of the array with $d$ will leave same remainder $0$, but that doesn't necessarily mean it is the largest possible answer.
For example, suppose the array is $A = \{2,8,14,26\}$. Then what will be the $gcd$ of array A? $gcd(2,8,14,26) = 2$. Dividing elements of $A$ with $2$ leaves us $0$. So is this our answer? No.
For array $A$, there exists a number greater than $2$ that leaves the same remainder. And that number is $3$. When we divide each element with $3$, it leaves us $2$ as the remainder.
The problem did not ask us to find the number that will leave $0$ as remainder. It asked us to find the largest number $d$ that leaves the same remainder. So for array $A$ the $gcd(A)$ is not the answer. Is $3$ our answer? No. The answer is given below in Example.
Using Congruence Relation
Let us rephrase the problem using congruence relation. Suppose there is an array with elements, $A=\{a,b,c\}$. We need to find the largest number $d$ that leaves the same remainder for each of its element.
Let us consider only $\{a,b\}$ for now. We need to find $d$ such that it leaves the same remainder when it divides $a$ and $b$. Meaning
$$a \: \equiv \: b \: \text{(mod d)} \\ a - b \: \equiv \: 0 \: \text{(mod d)}$$
What does this mean? It means, if $d$ leaves the same remainder when it divides $a$ and $b$, then it will leave no remainder when dividing $a-b$.
Using same logic, we can say that $b - c \: \equiv \: 0 \: \text{(mod d)}$. Therefore, if we find a number that divides $a-b$ and $b-c$, then that number will leave the same remainder when dividing $\{a,b,c\}$.
This idea can be extended for any number of elements in the array. So $d$ is such a number that leaves no remainder when it divides the difference of adjacent elements in the array.
But wait, there are multiple numbers that can divide the difference of adjacent elements. Which one should we take? Since we want the largest value of $d$, we will take the largest divisor that can divide all the difference of adjacent numbers. There is only one divisor that can divide all the adjacent differences, and that is $gcd( (a-b), (b-c) )$.
Therefore, if we have an array $A=\{a_1,a_2,a_3...a_n\}$, then $d = gcd( a_2 - a_1, a_3- a_2,...a_n - a_{n_1})$.
Careful about negative value of $gcd()$. Make sure you take the absolute value of $gcd()$.
Example
Let us get back to the example we were looking into before. Finding $d$ for the array $A = \{2,8,14,26\}$. We know that $d$ will divide the difference of adjacent elements completely. So let us make another array that will contain the difference of adjacent elements., $B = \{8-2, 14-8, 26-14\} = \{6,6,12\}$. Therefore, $d = gcd ( 6,6,12 ) = 6$.
Summary
- Let the array of elements be $A = \{a,b,c,d...\}$.
- $res \neq gcd(a,b,c,d...)$.
- $res = gcd ( a-b,b-c,c-d,...)$.
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long vlong;
vlong gcd ( vlong a, vlong b ) {
while ( b ) {
a = a % b;
swap ( a, b );
}
return a;
}
vlong arr[1010];
int main () {
while ( scanf ( "%d", &arr[0] ) != EOF ) {
if ( arr[0] == 0 ) break; //End of test case
//A new test case has started
int cur = 1;
//Take input
while ( 1 ) {
scanf ( "%lld", &arr[cur] );
if ( arr[cur] == 0 ) break;
else cur++;
}
vlong g = 0; //Start with 0 since gcd(0,x) = x.
for ( int i = 1; i < cur; i++ ) {
int dif = arr[i] - arr[i-1]; //Calculate difference
g = gcd ( g, dif ); //Find gcd() of differences
}
if ( g < 0 ) g *= -1; //In case gcd() comes out negative
printf ( "%lld\n", g );
}
return 0;
}
Labels: Analysis, GCD, Modular Arithmetic, Number Theory, UVa