Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/780.html

780. Reaching Points (Hard)

A move consists of taking a point (x, y) and transforming it to either (x, x+y) or (x+y, y).

Given a starting point (sx, sy) and a target point (tx, ty), return True if and only if a sequence of moves exists to transform the point (sx, sy) to (tx, ty). Otherwise, return False.

Examples:
Input: sx = 1, sy = 1, tx = 3, ty = 5
Output: True
Explanation:
One series of moves that transforms the starting point to the target is:
(1, 1) -> (1, 2)
(1, 2) -> (3, 2)
(3, 2) -> (3, 5)

Input: sx = 1, sy = 1, tx = 2, ty = 2
Output: False

Input: sx = 1, sy = 1, tx = 1, ty = 1
Output: True

Note:

• sx, sy, tx, ty will all be integers in the range [1, 10^9].

Related Topics:
Math

Solution 1.

Starting from (sx, sy) will get TLE since there are many branches we need to try.

Instead, we should start from (tx, ty) since there could be only a single valid route.

If tx > ty, the previous point must be (tx - ty, ty).

If tx < ty, the previous point must be (tx, ty - tx).

tx and ty can’t be the same otherwise the previous point will have 0 value in the coordinates.

If tx > ty, instead of keeping subtracting ty which could be slow when tx is very large and ty is very small, we do tx %= ty. The tx < ty case is symmetrical.

We loop until tx <= sx or ty <= sy, then we have two valid cases:

• sx == tx, ty >= sy and ty - sy is divisible by sx.
• sy == sy, sx >= tx and tx - sx is divisible by sy.

// OJ: https://leetcode.com/problems/reaching-points/
// Time: O(log(max(tx, ty)))
// Space: O(1)
// Ref: https://leetcode.com/problems/reaching-points/discuss/114856/JavaC%2B%2BPython-Modulo-from-the-End
class Solution {
public:
    bool reachingPoints(int sx, int sy, int tx, int ty) {
        while (sx < tx && sy < ty) {
            if (tx < ty) ty %= tx;
            else tx %= ty;
        }
        return (sx == tx && sy <= ty && (ty - sy) % sx == 0)
            || (sy == ty && sx <= tx && (tx - sx) % sy == 0);
    }
};

• Java
• C++
• Python
• Go

• class Solution {
      public boolean reachingPoints(int sx, int sy, int tx, int ty) {
          while (tx >= sx && ty >= sy) {
              if (tx > ty) {
                  if (ty > sy)
                      tx %= ty;
                  else
                      return (tx - sx) % ty == 0;
              } else if (tx < ty) {
                  if (tx > sx)
                      ty %= tx;
                  else
                      return (ty - sy) % tx == 0;
              } else
                  break;
          }
          return tx == sx && ty == sy;
      }
  }
  
  ############
  
  class Solution {
      public boolean reachingPoints(int sx, int sy, int tx, int ty) {
          while (tx > sx && ty > sy && tx != ty) {
              if (tx > ty) {
                  tx %= ty;
              } else {
                  ty %= tx;
              }
          }
          if (tx == sx && ty == sy) {
              return true;
          }
          if (tx == sx) {
              return ty > sy && (ty - sy) % tx == 0;
          }
          if (ty == sy) {
              return tx > sx && (tx - sx) % ty == 0;
          }
          return false;
      }
  }
  

• // OJ: https://leetcode.com/problems/reaching-points/
  // Time: O(log(max(tx, ty)))
  // Space: O(1)
  // Ref: https://leetcode.com/problems/reaching-points/discuss/114856/JavaC%2B%2BPython-Modulo-from-the-End
  class Solution {
  public:
      bool reachingPoints(int sx, int sy, int tx, int ty) {
          while (sx < tx && sy < ty) {
              if (tx < ty) ty %= tx;
              else tx %= ty;
          }
          return (sx == tx && sy <= ty && (ty - sy) % sx == 0)
              || (sy == ty && sx <= tx && (tx - sx) % sy == 0);
      }
  };
  

• class Solution:
      def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:
          while tx > sx and ty > sy and tx != ty:
              if tx > ty:
                  tx %= ty
              else:
                  ty %= tx
          if tx == sx and ty == sy:
              return True
          if tx == sx:
              return ty > sy and (ty - sy) % tx == 0
          if ty == sy:
              return tx > sx and (tx - sx) % ty == 0
          return False
  
  
  

• func reachingPoints(sx int, sy int, tx int, ty int) bool {
  	for tx > sx && ty > sy && tx != ty {
  		if tx > ty {
  			tx %= ty
  		} else {
  			ty %= tx
  		}
  	}
  	if tx == sx && ty == sy {
  		return true
  	}
  	if tx == sx {
  		return ty > sy && (ty-sy)%tx == 0
  	}
  	if ty == sy {
  		return tx > sx && (tx-sx)%ty == 0
  	}
  	return false
  }
  

All Problems

All Solutions