Reaching Points

hard math gcd greedy

Problem

Given start (sx,sy) and target (tx,ty) where each move sends (x,y) to (x+y,y) or (x,x+y), decide whether the target is reachable.

Inputsx=1, sy=1, tx=3, ty=5

Outputtrue

Reachable: (1,1)->(1,2)->(3,2)->(3,5).

input

def reachingPoints(sx, sy, tx, ty):
    while tx >= sx and ty >= sy:
        if tx == ty: break
        if tx > ty:
            if ty > sy: tx %= ty
            else: return (tx - sx) % ty == 0
        else:
            if tx > sx: ty %= tx
            else: return (ty - sy) % tx == 0
    return tx == sx and ty == sy

function reachingPoints(sx, sy, tx, ty) {
  while (tx >= sx && ty >= sy) {
    if (tx === ty) break;
    if (tx > ty) {
      if (ty > sy) tx %= ty;
      else return (tx - sx) % ty === 0;
    } else {
      if (tx > sx) ty %= tx;
      else return (ty - sy) % tx === 0;
    }
  }
  return tx === sx && ty === sy;
}

boolean reachingPoints(int sx, int sy, int tx, int ty) {
    while (tx >= sx && ty >= sy) {
        if (tx == ty) break;
        if (tx > ty) {
            if (ty > sy) tx %= ty;
            else return (tx - sx) % ty == 0;
        } else {
            if (tx > sx) ty %= tx;
            else return (ty - sy) % tx == 0;
        }
    }
    return tx == sx && ty == sy;
}

bool reachingPoints(int sx, int sy, int tx, int ty) {
    while (tx >= sx && ty >= sy) {
        if (tx == ty) break;
        if (tx > ty) {
            if (ty > sy) tx %= ty;
            else return (tx - sx) % ty == 0;
        } else {
            if (tx > sx) ty %= tx;
            else return (ty - sy) % tx == 0;
        }
    }
    return tx == sx && ty == sy;
}

Explanation

Each forward move turns (x, y) into (x+y, y) or (x, x+y). Searching forward branches in two ways and blows up, so the trick is to work backwards from the target. Backwards, the move is unambiguous: the larger coordinate must have been the one that grew, so we shrink it.

If tx > ty, the last step added ty to tx some number of times, so we undo all of them at once with tx %= ty (modulo = many subtractions in one shot). Symmetrically, if ty > tx we do ty %= tx. This is the same speed-up that makes the gcd algorithm fast.

We keep shrinking while both coordinates stay at or above the start. When one coordinate reaches the start row or column, we can't keep taking modulo (it would skip past the source). At that point we check the leftover with a single divisibility test, e.g. (ty - sy) % tx == 0, to see if the remaining gap is a whole number of steps.

Example: source (1,1), target (3,5). Since 5 > 3, do 5 % 3 = 2 → (3,2). Now 3 > 2, do 3 % 2 = 1 → (1,2). Now tx == sx == 1, and (2 - 1) % 1 == 0, so it is reachable → true.

Using modulo instead of one-by-one subtraction is what keeps this logarithmic even for huge coordinates.

Time: O(log(max(tx,ty))) Space: O(1)