Сложность: hard
Даны четыре целых числа sx, sy, tx и ty, верните true, если возможно преобразовать точку (sx, sy) в точку (tx, ty) с помощью некоторых операций, иначе верните false.
Допустимая операция для некоторой точки (x, y) заключается в преобразовании её либо в (x, x + y), либо в (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)
👨💻 Алгоритм:
1⃣Повторно вычитайте меньшее из {tx, ty} из большего из {tx, ty}.
2⃣Продолжайте вычитание, пока tx и ty больше или равны sx и sy соответственно.
3⃣Ответ будет true, если и только если в конечном итоге мы достигнем точки sx, sy.
😎 Решение:
class Solution {
func reachingPoints(_ sx: Int, _ sy: Int, _ tx: Int, _ ty: Int) -> Bool {
var tx = tx
var ty = ty
while tx >= sx && ty >= sy {
if sx == tx && sy == ty {
return true
}
if tx > ty {
tx -= ty
} else {
ty -= tx
}
}
return false
}
}Ставь 👍 и забирай 📚 Базу знаний