Last updated on January 19th, 2025 at 02:37 am

Here, we see a Reaching Points LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Array

Level of Question

Hard

Reaching Points LeetCode Solution

1. Problem Statement

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

2. Coding Pattern Used in Solution

The coding pattern used in this problem is “Reverse Engineering” or “Backtracking from Target”, where we need to determine if a target state can be reached from a starting state. Instead of simulating forward steps from the start, the algorithm works backward from the target to the start, reducing the problem size iteratively.

3. Code Implementation in Different Languages

3.1 Reaching Points C++

class Solution {
public:
    bool reachingPoints(int sx, int sy, int tx, int ty) {
        while(sx < tx && sy < ty){
            if(tx > ty) tx = tx%ty;
            else ty = 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;        
    }
};

3.2 Reaching Points Java

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

3.3 Reaching Points JavaScript

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

3.4 Reaching Points Python

class Solution(object):
    def reachingPoints(self, sx, sy, tx, ty):
        if tx==0 or ty==0: return (sx, sy)==(tx, ty)
        while not (sx==tx and sy==ty):
            if sx>tx or sy>ty: return False
            elif tx==ty: return ((0, ty)==(sx, sy) or (tx, 0)==(sx, sy))
            
            if ty>tx: 
                if tx==sx: return (ty-sy)%sx==0
                ty%=tx
            else: 
                if ty==sy: return (tx-sx)%sy==0
                tx%=ty
                     
        return True

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(log(max(tx, ty)))	O(1)
Java	O(log(max(tx, ty)))	O(1)
JavaScript	O(log(max(tx, ty)))	O(log(max(tx, ty)))
Python	O(log(max(tx, ty)))	O(1)

• The code uses a Reverse Engineering approach to solve the problem by working backward from the target (tx, ty) to the start (sx, sy).
• It reduces the problem size iteratively using modulo operations and checks for divisibility conditions to determine if the transformation is possible.
• The algorithm is efficient with logarithmic time complexity and minimal space usage.