We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
According to the problem, from (a,b) he can go, east: (a+b, b), north: (a, a+b), west: (a-b, b), south: (a, b-a) in this 2D grid
From (2) we can infer that any destination point will be of the form (a+n*b, b+m*a)
Mathematical property: adding or subtracting a multiple of one number to another does not change their greatest common divisor (GCD)
e.g. GCD(12, 8) = 4 = GCD(12+8*1, 8+12*2) = GCD(20, 32) = 4
With that in mind, given another point (x,y), we can infer that if we can reach that point, then it might be of the form (a+n*b, b+m*a)
hence their GCD must be the same if (x,y) is reachable from (a, b)
GCD function is
function gcd(a,b) { return (a % b == 0) ? b : gcd(b, a % b); }
Possible Path
You are viewing a single comment's thread. Return to all comments →
Can you please elaborate this further? How did you think and reason about it yourself in the first place?
Thanks in advance.
With that in mind, given another point (x,y), we can infer that if we can reach that point, then it might be of the form (a+n*b, b+m*a) hence their GCD must be the same if (x,y) is reachable from (a, b)
GCD function is function gcd(a,b) { return (a % b == 0) ? b : gcd(b, a % b); }
Hope that helps!