Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 780 with 22 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 780 # by problem number
lcpy gen -s reaching_points # by problem name
sx, sy, tx, and ty, return true if it is possible to convert the point (sx, sy) to the point (tx, ty) through some operations, or false otherwise.
The allowed operation on some point (x, y) is to convert it to either (x, x + y) or (x + y, y).
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
class Solution:
# Time: O(log(max(tx, ty)))
# Space: O(1)
def reaching_points(self, sx: int, sy: int, tx: int, ty: int) -> bool:
# Walk backwards from the target: the parent of (x, y) is unique, so
# collapse runs of same-axis moves with a modulo instead of subtracting.
while tx > sx and ty > sy:
if tx > ty:
tx %= ty
else:
ty %= tx
if tx == sx and ty == sy:
return True
if tx == sx and ty > sy:
return (ty - sy) % tx == 0
if ty == sy and tx > sx:
return (tx - sx) % ty == 0
return False
| Time | Space |
|---|---|
| O(log(max(tx, ty))) | O(1) |