Time complexity: O(2^N), where N = max(tx, ty). Each recursive call branches into two, and the tree can be exponential in height.

🧺 Space complexity: O(N) for the recursion stack, where N = max(tx, ty).

Complexity

The height of binary tree depends on tx,ty. All the values which are either greater then tx or ty will be discarded as from that we can't reach the tx,ty. Hence, the height of tree would be Max(tx,ty)= N ..total complexity O(2^N)

Method 2 – Iterative Solution (Modulo from the End)

Intuition

Instead of building the tree from the starting point (sx, sy), which leads to exponential branching, we can work backwards from the target (tx, ty). At each step, only one parent is possible, so the path is unique. This allows us to efficiently check if the target can be reduced to the start using reverse operations. The key insight is that, by using modulo, we can "jump" back multiple steps at once, avoiding time limit exceeded errors from repeated subtraction.

Approach

Work Backwards:
- Start from (tx, ty) and repeatedly subtract the smaller coordinate from the larger, simulating the reverse of the allowed moves.
- If tx > ty, set tx = tx % ty; if ty > tx, set ty = ty % tx.
- Continue until either tx < sx or ty < sy.
Check for Reachability:
- If we reach a point where one coordinate matches the start, check if the other can be reached by repeated additions (i.e., the difference is divisible by the start coordinate).
Efficiency:
- Using modulo instead of repeated subtraction makes the algorithm efficient, reducing the time complexity to logarithmic in the size of the target.

Note: This approach is closely related to the Euclidean algorithm for finding the greatest common divisor (GCD), as both use repeated modulo operations to reduce the problem size efficiently.

Dry Run

Suppose we have:

sx=1, sy=1, tx=1, ty=2

Consider node [1,2] as the left child of [1,1] in the tree above.

We reach the base case: [1,2] can be reached from [1,1] if ty >= sy (2 > 1) and (ty - sy) % sx == 0 (since (2-1)%1 == 0).

Why (ty - sy) % sx == 0? Because sy can only reach ty by repeated additions of sx (i.e., sy + k*sx = ty for some integer k). Thus, (ty - sy) / sx must be an integer, so the remainder is zero.

Code

[{"language":"C++","code":"class Solution {\npublic:\n\tbool reachingPoints(int sx, int sy, int tx, int ty) {\n\t\twhile (tx > sx && ty > sy) {\n\t\t\tif (tx > ty) tx %= ty;\n\t\t\telse ty %= tx;\n\t\t}\n\t\tif (sx == tx && sy <= ty && (ty - sy) % sx == 0) return true;\n\t\tif (sy == ty && sx <= tx && (tx - sx) % sy == 0) return true;\n\t\treturn false;\n\t}\n};","lang":"cpp"},{"language":"Go","code":"func reachingPoints(sx, sy, tx, ty int) bool {\n\tfor tx > sx && ty > sy {\n\t\tif tx > ty {\n\t\t\ttx %= ty\n\t\t} else {\n\t\t\tty %= tx\n\t\t}\n\t}\n\tif sx == tx && sy <= ty && (ty-sy)%sx == 0 {\n\t\treturn true\n\t}\n\tif sy == ty && sx <= tx && (tx-sx)%sy == 0 {\n\t\treturn true\n\t}\n\treturn false\n}","lang":"go"},{"language":"Java","code":"class Solution {\n\tpublic boolean reachingPoints(int sx, int sy, int tx, int

Related Tags