Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1348#google_vignette
Integer division between a dividend n and a divisor d yields a quotient q and a remainder r. q is the integer which maximizes q ∗ d such that q ∗ d ≤ n and r = n − q ∗ d. For any set of integers there is an integer d such that each of the given integers when divided by d leaves the same remainder. Input Each line of input contains a sequence of nonzero integer numbers separated by a space. The last number on each line is 0 and this number does not belong to the sequence. There will be at least 2 and no more than 1000 numbers in a sequence; not all numbers occuring in a sequence are equal. The last line of input contains a single 0 and this line should not be processed. Output For each line of input, output the largest integer which when divided into each of the input integers leaves the same remainder.
Sample Input 701 1059 1417 2312 0 14 23 17 32 122 0 14 -22 17 -31 -124 0 0
Sample Output 179 3 3
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
// idea:
// congruence relation
// if a%d == b%d, then (a-b)%d = 0
// thus d is a divisor than leave no remainder for (v2-v1)/d
// solution is thus to find the gcd of all (v1-v2), all pairs
// either gcd(v2-v1, v3-v2) or gcd(v3-v1,v3-v2) will work
using namespace std;
int gcd(int a, int b){
return a==0 ? b : gcd(b%a, a);
}
int main()
{
int first, val;
while(scanf("%d",&first), first != 0){
int res = 0;
while(scanf("%d",&val), val != 0)
res = gcd(res, val-first);
printf("%d\n", abs(res));
}
}Input
14 23 17 32 122 0
14 -22 17 -31 -124 0
0
Output
3
3
Demonstration
UVA Online Judge solution -10407-Simple division - UVA Online Judge solution in C,C++,java