Problem

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).

Examples

Example 1:

1
2
3
4
5
6
7

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:

1
2

Input: sx = 1, sy = 1, tx = 2, ty = 2
Output: false

Example 3:

1
2

Input: sx = 1, sy = 1, tx = 1, ty = 1
Output: true

Solution

This problem is similar to Construct Target Array With Multiple Sums.

Method 1 – Naive Approach (Top-Down DFS)

Intuition

At each point (x, y), we have two possible moves: either add y to x (resulting in (x + y, y)) or add x to y (resulting in (x, x + y)). This means that from any starting point, the set of reachable points forms a binary tree, where each node branches into two possible next points. The goal is to determine if there exists a sequence of such moves that transforms (sx, sy) into (tx, ty).

Approach

Recursive Exploration
  • Start from (sx, sy) and recursively try both possible moves at each step: (x + y, y) and (x, x + y).
  • If at any point we reach (tx, ty), return true.
  • If either coordinate exceeds the target (x > tx or y > ty), stop exploring that path (prune the search tree).
Visualization
  • The process can be visualized as a binary tree, where each node represents a possible state (x, y), and each branch corresponds to one of the two allowed moves.
---
title: sx=1, sy=1, tx=3, ty=5
---

graph TD
	A(1,1)
	B(2,1)
	C(1,2)
	D(3,1)
	E(2,3)
	F(1,3)
	G(3,2)
	H(2,5)
	I(1,5)
	J(5,1)
	K(3,5):::green
	L(5,2)

	A -- "+y" --> B
	A -- "+x" --> C
	B -- "+y" --> D
	B -- "+x" --> E
	C -- "+y" --> F
	C -- "+x" --> G
	E -- "+y" --> H
	F -- "+x" --> I
	D -- "+y" --> J
	G -- "+y" --> K
	G -- "+x" --> L

classDef green fill:#3CB371,stroke:#000,stroke-width:1px,color:#fff;

Code

1
2
3
4
5
6
7
8

class Solution {
public:
	bool reachingPoints(int sx, int sy, int tx, int ty) {
		if (sx == tx && sy == ty) return true;
		if (sx > tx || sy > ty) return false;
		return reachingPoints(sx + sy, sy, tx, ty) || reachingPoints(sx, sx + sy, tx, ty);
	}
};
1
2
3
4
5
6
7
8
9

func reachingPoints(sx, sy, tx, ty int) bool {
	if sx == tx && sy == ty {
		return true
	}
	if sx > tx || sy > ty {
		return false
	}
	return reachingPoints(sx+sy, sy, tx, ty) || reachingPoints(sx, sx+sy, tx, ty)
}
1
2
3
4
5
6
7

class Solution {
	public boolean reachingPoints(int sx, int sy, int tx, int ty) {
		if (sx == tx && sy == ty) return true;
		if (sx > tx || sy > ty) return false;
		return reachingPoints(sx + sy, sy, tx, ty) || reachingPoints(sx, sx + sy, tx, ty);
	}
}
1
2
3
4
5
6
7

class Solution {
	fun reachingPoints(sx: Int, sy: Int, tx: Int, ty: Int): Boolean {
		if (sx == tx && sy == ty) return true
		if (sx > tx || sy > ty) return false
		return reachingPoints(sx + sy, sy, tx, ty) || reachingPoints(sx, sx + sy, tx, ty)
	}
}
1
2
3
4
5
6
7

class Solution:
	def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:
		if sx == tx and sy == ty:
			return True
		if sx > tx or sy > ty:
			return False
		return self.reachingPoints(sx + sy, sy, tx, ty) or self.reachingPoints(sx, sx + sy, tx, ty)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
	pub fn reaching_points(sx: i32, sy: i32, tx: i32, ty: i32) -> bool {
		if sx == tx && sy == ty {
			return true;
		}
		if sx > tx || sy > ty {
			return false;
		}
		Solution::reaching_points(sx + sy, sy, tx, ty) || Solution::reaching_points(sx, sx + sy, tx, ty)
	}
}
1
2
3
4
5

function reachingPoints(sx: number, sy: number, tx: number, ty: number): boolean {
	if (sx === tx && sy === ty) return true;
	if (sx > tx || sy > ty) return false;
	return reachingPoints(sx + sy, sy, tx, ty) || reachingPoints(sx, sx + sy, tx, ty);
}

Complexity

  • ⏰ 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

  1. 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.

  2. 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).

  3. 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:

1

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
	bool reachingPoints(int sx, int sy, int tx, int ty) {
		while (tx > sx && ty > sy) {
			if (tx > ty) tx %= ty;
			else ty %= tx;
		}
		if (sx == tx && sy <= ty && (ty - sy) % sx == 0) return true;
		if (sy == ty && sx <= tx && (tx - sx) % sy == 0) return true;
		return false;
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func reachingPoints(sx, sy, tx, ty int) bool {
	for tx > sx && ty > sy {
		if tx > ty {
			tx %= ty
		} else {
			ty %= tx
		}
	}
	if sx == tx && sy <= ty && (ty-sy)%sx == 0 {
		return true
	}
	if sy == ty && sx <= tx && (tx-sx)%sy == 0 {
		return true
	}
	return false
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
	public boolean reachingPoints(int sx, int sy, int tx, int ty) {
		while (tx > sx && ty > sy) {
			if (tx > ty) tx %= ty;
			else ty %= tx;
		}
		if (sx == tx && sy <= ty && (ty - sy) % sx == 0) return true;
		if (sy == ty && sx <= tx && (tx - sx) % sy == 0) return true;
		return false;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
	fun reachingPoints(sx: Int, sy: Int, tx: Int, ty: Int): Boolean {
		var tx = tx
		var ty = ty
		while (tx > sx && ty > sy) {
			if (tx > ty) tx %= ty
			else ty %= tx
		}
		if (sx == tx && sy <= ty && (ty - sy) % sx == 0) return true
		if (sy == ty && sx <= tx && (tx - sx) % sy == 0) return true
		return false
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
	def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:
		while tx > sx and ty > sy:
			if tx > ty:
				tx %= ty
			else:
				ty %= tx
		if sx == tx and sy <= ty and (ty - sy) % sx == 0:
			return True
		if sy == ty and sx <= tx and (tx - sx) % sy == 0:
			return True
		return False
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
	pub fn reaching_points(sx: i32, sy: i32, mut tx: i32, mut ty: i32) -> bool {
		while tx > sx && ty > sy {
			if tx > ty {
				tx %= ty;
			} else {
				ty %= tx;
			}
		}
		if sx == tx && sy <= ty && (ty - sy) % sx == 0 {
			return true;
		}
		if sy == ty && sx <= tx && (tx - sx) % sy == 0 {
			return true;
		}
		false
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

function reachingPoints(sx: number, sy: number, tx: number, ty: number): boolean {
	while (tx > sx && ty > sy) {
		if (tx > ty) {
			tx %= ty;
		} else {
			ty %= tx;
		}
	}
	if (sx === tx && sy <= ty && (ty - sy) % sx === 0) return true;
	if (sy === ty && sx <= tx && (tx - sx) % sy === 0) return true;
	return false;
}

Complexity

  • ⏰ Time complexity: O(log(min(tx, ty))) due to the modulo operations reducing the larger coordinate quickly.
  • 🧺 Space complexity: O(1) since only a constant amount of extra space is used.