3

I recently had an interview and my algorithm only passed all test cases except one and I can't figure out why. The problem I need to tackle was:

Given a standing point(a,b) in an 2D grid is it possible to reach destination point(x, y) or not. The only operation he can do is to move to point(a+b, b) or (a, a+b) from some point (a,b).

I tried to solve it by using gcd. e.g. If gcd(a,b) = gcd(x,y) then its is possible else not. The intuition was if k be the gcd of a & b. then, k would also divide (a+b). I used the following algorithm to calculate gcd:

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

EDIT: Also the numbers a,b,x and y are all positive integers.

Dashing Boy
  • 477
  • 2
  • 10
  • 21
  • For clarification. Say you start at position `(a0, b0)`. At any given time, you are at position `(ai, bi)`. Then, the next positions you can go to are a) `(ai + b0, bi)` and `(ai, a0 + bi)` or b) `(ai + bi, bi)` and `(ai, ai + bi)`? – jdehesa Apr 04 '19 at 16:35
  • It's a necessary condition but why do you think it's sufficient? Can you move from (5,2) to (7,3)? – n. m. could be an AI Apr 04 '19 at 16:39
  • I don't exactly remember what were the condition but one example that I remember was something like: (1, 1) -> (2, 3) and the steps were (1+1, 1) -> (2, 1+2) -> (2, 3) and the example of (5,2) to (7,3) is not possible because I can't reach by adding a+b. – Dashing Boy Apr 04 '19 at 16:46
  • 2
    Possible duplicate of [Can a Robot reach a Point (x, y)?](https://stackoverflow.com/questions/52039541/can-a-robot-reach-a-point-x-y) – Photon Apr 04 '19 at 17:22
  • Yes, I think it's the same question however I still can't figure out why GCD didn't work. – Dashing Boy Apr 04 '19 at 17:42
  • So you're saying you can reach (1, 2) from (2, 1)? – gus Apr 04 '19 at 19:11

2 Answers2

1

GCD(3,7) = GCD(7,3) but neither is reachable from the other. Your condition is necessary but not sufficient.

Note that there is a unique possible predecessor to every point. I.e. for the point (a,b) if a>b then the predecessor is (a-b,b) otherwise the predecessor is (a, b-a).

Dave
  • 7,460
  • 3
  • 26
  • 39
0

You now have 2 questions on the post:

  1. How do I solve the algorithm?
    Photon's link covers this well.
  2. Why didn't GCD work?

GCD is a necessary, but not sufficient condition.

True, if a=b, then (x, y) is reachable iff GCD(x, y) = a = b. However, this does not generalize to all problem pairs. The trivial counterexample is trying to reach (1, N) from (N,1), where N>1. Another is (2, 3) => (4, 5).

So, let's get to the qualitative part: "I can't figure out ...". I suspect that the problem is where you see a similarity between Euclid's algorithm and your addition step. Even stronger, the "backwards" algorithm in the link suggests that Euclid's algorithm applies.

It can, in a way, but not as simply and universally as you've tried to use it. Think of the problem as a graph on the positive-integer lattice in the Cartesian plane. The permitted operations (directed edges) define how you can move from one point to another.

The key term here is directed: once you've "moved" from a starting point to one that defines the GCD in your system, you do not have the freedom to retrace those steps. You move either forward or backward through your graph space.

For instance, although your backward transitions allow you to move from (4, 1) to (1, 1) or from (1, 4) to (1, 1), you cannot use this to conclude a path from (4, 1) to (1, 4): half of those moves are in a direction not permitted.

Does that help dispel the confusion?

Prune
  • 76,765
  • 14
  • 60
  • 81