780. Reaching Points
https://leetcode.com/problems/reaching-points/description/
Given four integers 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).
Example 1:
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)
Example 2:
Input: sx = 1, sy = 1, tx = 2, ty = 2 Output: false
Example 3:
Input: sx = 1, sy = 1, tx = 1, ty = 1 Output: true
Constraints:
1 <= sx, sy, tx, ty <= 109
---
Intuition
Moving from source to target - binary tree
Whether path exists - Explore all paths - O(2 ^ h)
worst case - skewed tree - O(2 ^ N)
Faster - move from target to source
while neither x and y reached, reduce bigger dimension
bigger dimension was incremented in last step
decrement with modulus for skewed tree
modulus is aster than stepwise decrement with subtraction
when one dimension matches
again check if difference of bigger dimension is a modulus of smaller dimension
---
Time - O(2 ^ h)
h = log N
With this approach worst case is balanced tree
skewed tree will perform faster due to modulus operator
---