- Practice
- Mathematics
- Fundamentals
- Possible Path
- Discussions

# Possible Path

# Possible Path

+ 20 comments 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.

+ 5 comments 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.

+ 1 comment 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!

+ 1 comment To avoid timeouts, use Euclidean algorithm https://en.wikipedia.org/wiki/Euclidean_algorithm

+ 3 comments 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

Sort 82 Discussions, By:

Please Login in order to post a comment