780. Reaching Points Solution & Explanation

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

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 <= 10⁹

Approach overview

Problem Overview: Starting from a point (sx, sy), you can transform it using two operations: (x, y) → (x + y, y) or (x, y) → (x, x + y). The task is to determine whether these operations can produce the target point (tx, ty).

Approach 1: Recursive Backtracking (Exponential Time)

This approach simulates the process exactly as described in the problem. From (sx, sy), recursively apply both operations and explore the resulting states until either the target (tx, ty) is reached or the coordinates exceed the target values. Because each state branches into two possibilities, the search tree grows quickly and leads to exponential time complexity O(2^k), where k is the number of operations performed. Space complexity is O(k) due to the recursion stack. While this approach demonstrates the mechanics of the transformation well, it becomes infeasible for large coordinates since the search space explodes.

Approach 2: Reverse Operation with Modulo Optimization (O(log n))

The key observation is that the forward process only increases values. Instead of building from (sx, sy), work backward from (tx, ty). If the last move produced (tx, ty), then the previous state must have been either (tx - ty, ty) or (tx, ty - tx). Repeated subtraction simulates reversing the operation, but doing this one step at a time would still be slow for large numbers. A faster trick uses the modulo operator: if tx > ty, replace tx with tx % ty; if ty > tx, replace ty with ty % tx. This compresses many subtraction steps into a single operation, similar to the Euclidean algorithm used for GCD. Continue until either the coordinates match the start point or one coordinate drops below the start. Time complexity becomes O(log(max(tx, ty))) and space complexity is O(1). The solution relies heavily on reasoning about number transitions, which connects naturally with Math and Number Theory patterns.

Recommended for interviews: The reverse modulo approach is what interviewers typically expect. It shows you can transform a brute-force forward simulation into a mathematical reduction problem. Discussing the recursive backtracking approach first demonstrates understanding of the rules, while transitioning to the reverse greedy strategy highlights optimization skills and familiarity with patterns related to Recursion and arithmetic reasoning.

Approach 1: Reverse Operation Approach

The goal could be efficiently approached by reversing the operations. Instead of trying to reach (tx, ty) from (sx, sy), we attempt to determine whether (sx, sy) can be reached from (tx, ty) using reverse operations. This is achieved by repeatedly applying the inverse operations: (x, x+y) can be reverted to (x, y), and (x+y, y) can be reverted to (x, y). The main idea is to use modulus operations when x != y.

Python

class Solution:
    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:
        while tx > sx and ty > sy and tx != ty:
            if tx > ty:
                tx %= ty
            else:
                ty %= tx
        if tx < sx or ty < sy:
            return False
        return (ty - sy) % sx == 0 if tx == sx else (tx - sx) % sy == 0

Java

public class Solution {
    public boolean reachingPoints(int sx, int sy, int tx, int ty) {
        while (tx > sx && ty > sy && tx != ty) {
            if (tx > ty) tx %= ty;
            else ty %= tx;
        }
        if (tx < sx || ty < sy) return false;
        if (tx == sx) return (ty - sy) % sx == 0;
        return (tx - sx) % sy == 0;
    }
}

C++

#include <iostream>
using namespace std;

class Solution {
public:
    bool reachingPoints(int sx, int sy, int tx, int ty) {
        while (tx > sx && ty > sy && tx != ty) {
            if (tx > ty) tx %= ty;
            else ty %= tx;
        }
        if (tx < sx || ty < sy) return false;
        if (tx == sx) return (ty - sy) % sx == 0;
        return (tx - sx) % sy == 0;
    }
};

JavaScript

var reachingPoints = function(sx, sy, tx, ty) {
    while (tx > sx && ty > sy && tx != ty) {
        if (tx > ty) tx %= ty;
        else ty %= tx;
    }
    if (tx < sx || ty < sy) return false;
    return tx == sx ? (ty - sy) % sx === 0 : (tx - sx) % sy === 0;
};

#include <stdbool.h>
bool reachingPoints(int sx, int sy, int tx, int ty) {
    while (tx > sx && ty > sy && tx != ty) {
        if (tx > ty) tx %= ty;
        else ty %= tx;
    }
    if (tx < sx || ty < sy) return false;
    if (tx == sx) return (ty - sy) % sx == 0;
    return (tx - sx) % sy == 0;
}

public class Solution {
    public bool ReachingPoints(int sx, int sy, int tx, int ty) {
        while (tx > sx && ty > sy && tx != ty) {
            if (tx > ty) tx %= ty;
            else ty %= tx;
        }
        if (tx < sx || ty < sy) return false;
        return tx == sx ? (ty - sy) % sx == 0 : (tx - sx) % sy == 0;
    }
}

Python makes this logic concise with its simple syntax. The logic is identical, where reverse operations are applied until reduction is achieved or deemed impossible. Modulus operations work well in reducing the situation to its origin.

Complexity

Time Complexity: O(log(max(tx, ty)))
Space Complexity: O(1)

Try this approach in the editor

Approach 2: Recursive Backtracking Approach

Another strategy involves recursive backtracking, where the function makes recursive calls to simulate both directions (x + y, y) and (x, x + y) to reach the target point (tx, ty) from the start point (sx, sy). Although less efficient compared to the reverse operation method due to its depth, it's an introductory way to explore the possibilities.

Python

class Solution:
    def reach(self, sx, sy, tx, ty):
        if sx > tx or sy > ty:
            return False
        if sx == tx and sy == ty:
            return True
        return self.reach(sx + sy, sy, tx, ty) or self.reach(sx, sy + sx, tx, ty)
    
    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:
        return self.reach(sx, sy, tx, ty)

Java

public class Solution {
    public boolean reach(int sx, int sy, int tx, int ty) {
        if (sx > tx || sy > ty) return false;
        if (sx == tx && sy == ty) return true;
        return reach(sx + sy, sy, tx, ty) || reach(sx, sy + sx, tx, ty);
    }
    public boolean reachingPoints(int sx, int sy, int tx, int ty) {
        return reach(sx, sy, tx, ty);
    }
}

C++

#include <iostream>
using namespace std;

class Solution {
public:
    bool reach(int sx, int sy, int tx, int ty) {
        if (sx > tx || sy > ty) return false;
        if (sx == tx && sy == ty) return true;
        return reach(sx + sy, sy, tx, ty) || reach(sx, sy + sx, tx, ty);
    }
    bool reachingPoints(int sx, int sy, int tx, int ty) {
        return reach(sx, sy, tx, ty);
    }
};

JavaScript

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

#include <stdbool.h>
bool reach(int sx, int sy, int tx, int ty) {
    if (sx > tx || sy > ty) return false;
    if (sx == tx && sy == ty) return true;
    return reach(sx + sy, sy, tx, ty) || reach(sx, sy + sx, tx, ty);
}
bool reachingPoints(int sx, int sy, int tx, int ty) {
    return reach(sx, sy, tx, ty);
}

public class Solution {
    public bool Reach(int sx, int sy, int tx, int ty) {
        if (sx > tx || sy > ty) return false;
        if (sx == tx && sy == ty) return true;
        return Reach(sx + sy, sy, tx, ty) || Reach(sx, sy + sx, tx, ty);
    }
    public bool ReachingPoints(int sx, int sy, int tx, int ty) {
        return Reach(sx, sy, tx, ty);
    }
}

The Python recursive approach pursues feasibility by exploring both possible moves repeatedly until the base condition (goal reached or surpassed) is met. It clearly suffers from larger-than-efficient computation with high endpoint values due to the non-optimal nature of recursive exploration.

Complexity

Time Complexity: Exponentially high
Space Complexity: Recursion depth based

Try this approach in the editor

Approach 3: Default Approach

func reachingPoints(sx int, sy int, tx int, ty int) bool {
	for tx > sx && ty > sy && tx != ty {
		if tx > ty {
			tx %= ty
		} else {
			ty %= tx
		}
	}
	if tx == sx && ty == sy {
		return true
	}
	if tx == sx {
		return ty > sy && (ty-sy)%tx == 0
	}
	if ty == sy {
		return tx > sx && (tx-sx)%ty == 0
	}
	return false
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Reverse Operation Approach	Time Complexity: O(log(max(tx, ty))) Space Complexity: O(1)
Recursive Backtracking Approach	Time Complexity: Exponentially high Space Complexity: Recursion depth based
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Recursive Backtracking	O(2^k)	O(k)	Useful for understanding the forward transformation rules or demonstrating brute-force reasoning in interviews
Reverse Operation with Modulo Optimization	O(log(max(tx, ty)))	O(1)	Optimal solution for large coordinates; uses mathematical reduction similar to the Euclidean algorithm

Frequently asked questions

Is Reaching Points easy or hard?

Reaching Points is labeled Hard because the forward process appears exponential and many candidates initially attempt brute-force recursion. The difficulty lies in recognizing that reversing the operations and applying modulo reduces the problem to a logarithmic mathematical process.

Reaching Points Python/Java solution

Most implementations follow the reverse modulo logic. Starting from (tx, ty), reduce the larger coordinate using modulo until it approaches (sx, sy). This logic translates directly across languages such as Python, Java, C++, C#, and JavaScript because it only uses simple arithmetic and loops.

How to solve Reaching Points in O(log n)?

Start from the target point (tx, ty) and repeatedly reduce the larger coordinate using modulo. If tx > ty, set tx = tx % ty; otherwise set ty = ty % tx. Continue until one coordinate becomes less than the corresponding start coordinate. Finally check if the remaining difference can be matched by repeated additions from the start point.

What is the best approach for Reaching Points?

The most efficient solution works backward from (tx, ty) to (sx, sy). Instead of simulating every forward move, repeatedly reduce the larger coordinate using modulo: tx %= ty or ty %= tx. This mirrors the Euclidean algorithm and reduces the search space quickly. The time complexity becomes O(log(max(tx, ty))) with constant space.

Is Reaching Points asked at Google/Amazon/Meta?

Reaching Points is considered a classic math and reasoning problem that appears in interviews at large tech companies including Google, Amazon, and Meta. It tests the ability to reverse operations and recognize patterns similar to the Euclidean GCD algorithm rather than brute-force simulation.

What data structure is used in Reaching Points?

The optimal solution does not rely on complex data structures. It primarily uses arithmetic operations and a loop while applying modulo reductions. The problem falls under math and number theory reasoning rather than typical structures like arrays, stacks, or graphs.

What is the time complexity of Reaching Points?

The optimal reverse-modulo approach runs in O(log(max(tx, ty))) time because each modulo operation significantly reduces one coordinate. Space complexity is O(1) since the algorithm uses only a few variables. A naive recursive backtracking solution can grow exponentially, making it impractical for large inputs.

Reaching Points solution and explanation

The problem

Approach overview

Approach 1: Reverse Operation Approach

Approach 2: Recursive Backtracking Approach

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Reaching Points solution and explanation

The problem

Approach overview

Approach 1: Reverse Operation Approach

Approach 2: Recursive Backtracking Approach

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems