Find the minimum difference between Shifted tables of two numbers

http://www.geeksforgeeks.org/find-the-difference-between-shifted-tables-of-two-numbers/

Given two numbers ‘a’ and ‘b’. Find the minimum difference between any terms in shifted infinite tables of ‘a’ and ‘b’, given shifts ‘x’ and ‘y’, where x, y >= 0.

Let us consider a = 6 and b = 16. Infinite tables of these numbers are.

Table of a : 6, 12, 18, 24, 30, 36, 42, 48.….
Table of b : 16, 32, 48, 64, 80, 96, 112, 128…..

Let given shifts be x = 5 and y = 2
Shifted Table of a : 11, 17, 23, 29, 35, 41, 47 …
Shifted Table of b : 18, 34, 50, 66, 82, 98, 114 …

The minimum difference between any two terms of above two shifted tables is 1 (See colored terms). So the output should be 1.

// Utility function to find GCD of a and b

int gcd(int a, int b)

{

    while (b != 0)

    {

        int t = b;

        b = a % b;

        a = t;

    }

    return a;

}

// Returns minimum difference between

// any two terms of shifted tables of 'a'

// and 'b'. 'x' is shift in table of 'a'

// and 'y' is shift in table of 'b'.

int findMinDiff(int a, int b, int x, int y)

{

    // Calculate gcd of a nd b

    int g  = gcd(a,b);

    // Calculate difference between x and y

    int diff = abs(x-y) % g;

    return min(diff, g - diff);

}

Complexity: O(log n), to compute the GCD.

How does this work?

After shifting tables become (Assuming y > x and diff = y-x)
a+x, 2a+x, 3a+x, .. ab+x, …. and b+y, 2b+y, 3b+y, …., ab+y, ….

In general, difference is, abs[(am + x) – (bn + y)] where m >= 1 and n >= 1

An upper bound on minimum difference is “abs(x – y)”. We can always get this difference by putting m = b and n = a.

How can we reduce the absolute difference below “abs(x – y)”?
Let us rewrite “abs[(am + x) – (bn + y)]” as abs[(x – y) – (bn – am)]

Let the GCD of ‘a’ and ‘b’ be ‘g’. Let us consider the table of ‘g’. The table has all terms like a, 2a, 3a, … b, 2b, 3b, … and also the terms (bn – am) and (am – bn).