• + 1 comment
    1. Point (a,b) is the start
    2. 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
    3. From (2) we can infer that any destination point will be of the form (a+n*b, b+m*a)
    4. 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
    5. 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)

    6. GCD function is function gcd(a,b) { return (a % b == 0) ? b : gcd(b, a % b); }

    Hope that helps!