Sort 82 Discussions, By:
Please Login in order to post a comment
According to the definition of Greatest Common Divisior, if m is any integer, then gcd(a + m * b, b) = gcd(a, b).
(In this particular problem m = 1 or m = -1 in each step.) Therefore, the gcd of
(a + b, b), (a, a + b), (a - b, b) and (a, a - b)
will be the same as the gcd of (a, b). Therefore, in order to move to the target point, the gcd of the target point should be equal to the gcd of the starting point.
gcd(a + m * b, b) = gcd(a, b)
I hate to admit my ignorance here. This may be an elegant solution but it's not at all clear to me why this gcd test works. Sorry, I have a BS in Mathematics and it's still not clear. Some discussion of why this works would be nice.
if x-a is a multiple of b and y-b is a multiple of a then that path is possible!! Is there somethimg wrong in the logic?if yes then pls explain!
To avoid timeouts, use Euclidean algorithm https://en.wikipedia.org/wiki/Euclidean_algorithm
as x- axis can be moved by only a+b or a-b operation to reach x,
so (x-a) should be multiple of b .. then only by adding b times some int we can reach x from a. similarily for y .. but this is giving wrong ans .. please tell where i am going wrong