Skip to content

780. Reaching Points 👍

  • Time: $O(\log\max(tx, ty))$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
 public:
  bool reachingPoints(int sx, int sy, int tx, int ty) {
    while (sx < tx && sy < ty)
      if (tx > ty)
        tx %= ty;
      else
        ty %= tx;

    return sx == tx && sy <= ty && (ty - sy) % sx == 0 ||
           sy == ty && sx <= tx && (tx - sx) % sy == 0;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
  public boolean reachingPoints(int sx, int sy, int tx, int ty) {
    while (sx < tx && sy < ty)
      if (tx > ty)
        tx %= ty;
      else
        ty %= tx;

    return                                             //
        sx == tx && sy <= ty && (ty - sy) % tx == 0 || //
        sy == ty && sx <= tx && (tx - sx) % ty == 0;
  }
}

1
2
3
4
5
6
7
class Solution:
  def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:
    while sx < tx and sy < ty:
      tx, ty = tx % ty, ty % tx

    return (sx == tx and sy <= ty and (ty - sy) % tx == 0 or
            sy == ty and sx <= tx and (tx - sx) % ty == 0)