## Friday, June 10, 2016

### 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 : 1834, 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).