LeetCode Solutions

780. Reaching Points

Time: $O(\log N)$, where $N = \max(tx, ty)$

Space: $O(1)$

			

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;
  }
};
			

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;
  }
}
			

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