Leetcode 780. Reaching Points
Problem Explanation
The aim of this problem is to determine whether a target point (tx, ty) can be reached from a starting point (sx, sy) by performing certain kinds of moves. A single move allows the repositioning of a point (x, y) to either point (x, x+y) or (x+y, y). In this context, we'd like to know if a sequence of such moves can take us from a starting point to a target point.
As an example, if we start at point (1, 1) and aim to reach point (3, 5), our sequence of moves might look like this:
- (1, 1) -> (1, 2)
- (1, 2) -> (3, 2)
- (3, 2) -> (3, 5)
From this sequence, we can see that it is possible to reach the target and would therefore return True
.
Solution Approach
The main problem can be solved using an approach which involves execution of repetitive terms until a certain condition holds, thus a "While" loop. Basically, while sx < tx and sy < ty, we perform one of two operations depending on whether tx>ty, or the other way around.
The condition stops when sx == tx and sy <= ty, where (ty - sy) % sx == 0. Alternatively, when sy == ty and sx <= tx where (tx - sx) % sy == 0. These conditions are important as they intelligently map out the sequence of steps needed to arrive at the target coordinates.
Python Solution
1 2python 3class Solution: 4 def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool: 5 while sx < tx and sy < ty: 6 if tx > ty: 7 tx %= ty 8 else: 9 ty %= tx 10 11 return sx == tx and sy <= ty and (ty - sy) % sx == 0 or sy == ty and sx <= tx and (tx - sx) % sy == 0
Java Solution
1 2java 3class Solution { 4 public boolean reachingPoints(int sx, int sy, int tx, int ty) { 5 while (sx < tx && sy < ty) 6 if (tx > ty) 7 tx %= ty; 8 else 9 ty %= tx; 10 11 return sx == tx && sy <= ty && (ty - sy) % sx == 0 || sy == ty && sx <= tx && (tx - sx) % sy == 0; 12 } 13}
Javascript Solution
1 2javascript 3class Solution { 4 reachingPoints(sx, sy, tx, ty) { 5 while (sx < tx && sy < ty) 6 if (tx > ty) 7 tx %= ty; 8 else 9 ty %= tx; 10 11 return sx === tx && sy <= ty && (ty - sy) % sx === 0 || sy === ty && sx <= tx && (tx - sx) % sy === 0; 12 } 13}
C++ Solution
1
2cpp
3class Solution {
4public:
5 bool reachingPoints(int sx, int sy, int tx, int ty) {
6 while (sx < tx && sy < ty)
7 if (tx > ty)
8 tx %= ty;
9 else
10 ty %= tx;
11
12 return sx == tx && sy <= ty && (ty - sy) % sx == 0 || sy == ty && sx <= tx && (tx - sx) % sy == 0;
13 }
14};
C# Solution
1
2csharp
3public class Solution {
4 public bool ReachingPoints(int sx, int sy, int tx, int ty) {
5 while (sx < tx && sy < ty) {
6 if (tx > ty)
7 tx %= ty;
8 else
9 ty %= tx;
10 }
11
12 return sx == tx && sy <= ty && (ty - sy) % sx == 0 || sy == ty && sx <= tx && (tx - sx) % sy == 0;
13 }
14}
In all the solutions above, we start by checking whether the start coordinates are less than the target ones. If they are, we perform an operation to decrease the gap. Once the gap is constant, we check if the start and target coordinates are equal or if the difference between the target and start coordinates is divisible by the start coordinates. This ensures that we can reach the target from the start.
Ruby Solution
1 2ruby 3class Solution 4 def reaching_points(sx, sy, tx, ty) 5 while sx < tx && sy < ty 6 if tx > ty 7 tx %= ty 8 else 9 ty %= tx 10 end 11 end 12 13 return sx == tx && sy <= ty && (ty - sy) % sx == 0 || sy == ty && sx <= tx && (tx - sx) % sy == 0 14 end 15end
Swift Solution
1
2swift
3class Solution {
4 func reachingPoints(_ sx: Int, _ sy: Int, _ tx: Int, _ ty: Int) -> Bool {
5 var tx = tx
6 var ty = ty
7
8 while sx < tx && sy < ty {
9 if tx > ty {
10 tx %= ty
11 } else {
12 ty %= tx
13 }
14 }
15
16 return sx == tx && sy <= ty && (ty - sy) % sx == 0 || sy == ty && sx <= tx && (tx - sx) % sy == 0
17 }
18}
PHP Solution
1
2php
3class Solution {
4 function reachingPoints($sx, $sy, $tx, $ty) {
5 while ($sx < $tx && $sy < $ty)
6 if ($tx > $ty)
7 $tx %= $ty;
8 else
9 $ty %= $sx;
10
11 return $sx == $tx && $sy <= $ty && ($ty - $sy) % $sx == 0 || $sy == $ty && $sx <= $tx && ($tx - $sx) % $sy == 0;
12 }
13}
Conclusion
By using a while loop and some conditions, we are essentially trying to trace our steps backward from the target to the start. This approach of solving the problem is a clear demonstration of how to use loops and conditionals to create a clear path from the start to end, regardless of the programming language. It also highlights how simple mathematical operations can be used effectively in solving seemingly complex computational problems.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.