Solution For Reaching Points

The Reaching Points problem on LeetCode asks us to find if we can reach a target point (tx, ty) starting from a source point (sx, sy) using only the following two operations:

• Add the coordinates (x, x+y).
• Add the coordinates (x+y, y).

We can assume that the source point (sx, sy) is always (1, 1).

To solve this problem, we can use a recursive approach where we try all possible paths from the source point to the target point.

Let’s define a recursive function canReach(sx, sy, tx, ty) that returns true if we can reach the target point (tx, ty) starting from the source point (sx, sy), and false otherwise.

The base case of the recursion is when the source point coincides with the target point (sx == tx and sy == ty). In this case, we can reach the target point, so we return true.

For the recursive case, we try all possible paths from the source point by applying the two operations described above. If any of these paths reaches the target point, we return true. Otherwise, we return false.

Here’s the complete Python code implementation of the canReach function:

def canReach(sx, sy, tx, ty):
if sx == tx and sy == ty:
# Base case: we have reached the target point.
return True

if sx > tx or sy > ty:
    # We have gone beyond the target point, so
    # we cannot reach it.
    return False

# Try all possible paths and return true if
# any of them reaches the target point.
return canReach(sx + sy, sy, tx, ty) or canReach(sx, sx + sy, tx, ty)

This algorithm has a time complexity of O(2^(tx+ty)) in the worst case, which is not very efficient. However, we can optimize it using a bottom-up approach with dynamic programming.

We can use a two-dimensional boolean array reachable[i][j] to store whether we can reach the point (i, j) starting from the source point (1, 1). We can initialize the reachable array with reachable[1][1] = True and reachable[i][j] = False for all other points.

Then, we can iteratively compute the value of reachable[i][j] for all points (i, j) such that i <= tx and j <= ty. For each such point, we can set reachable[i][j] to true if it is reachable from any of the previously computed points (i – j, j) or (i, j – i).

Here’s the Python code implementation of the dynamic programming approach:

def canReach(sx, sy, tx, ty):
# Initialize the reachable array
reachable = [[False] * (ty+1) for _ in range(tx+1)] reachable[1][1] = True

# Compute the values of the reachable array
for i in range(1, tx+1):
    for j in range(1, ty+1):
        if i == 1 and j == 1:
            # Already initialized
            continue
        if i >= j and reachable[i-j][j]:
            reachable[i][j] = True
            continue
        if j >= i and reachable[i][j-i]:
            reachable[i][j] = True
            continue

# Return whether the target point is reachable
return reachable[tx][ty]

Step by Step Implementation For Reaching Points

We can solve this problem with a simple while loop. The idea is to keep track of the current x and y position, and move either x or y one step at a time until we reach the target position.

int reachingPoints(int sx, int sy, int tx, int ty) {
    while (tx >= sx && ty >= sy) {
        if (tx == ty) break;
        if (tx > ty) {
            tx -= ty;
        } else {
            ty -= tx;
        }
    }
    return (tx == sx && ty == sy);
}

def reachingPoints(sx, sy, tx, ty):
    # Base cases 
    if sx > tx or sy > ty: 
        return False
    if sx == tx and sy == ty: 
        return True
    
    # Since we need to find a path from s to t, 
    # we move towards t as long as we can. 
    # Once we are stuck, we backtrack and try other 
    # paths by incrementing one of the coordinates 
    # used to reach t. 
    
    # Move horizontally 
    if sx == tx: 
        return (ty - sy) % sx == 0
    
    # Move vertically 
    if sy == ty: 
        return (tx - sx) % sy == 0
    
    # Move diagonally 
    return reachingPoints(sx, sx + sy, tx, ty) or \
           reachingPoints(sx + sy, sy, tx, ty)

/**
 * @param {number} sx
 * @param {number} sy
 * @param {number} tx
 * @param {number} ty
 * @return {boolean}
 */
var reachingPoints = function(sx, sy, tx, ty) {
    // while loop that iterates through every possible point
    // check if the target point is reached
    while (tx >= sx && ty >= sy) {
        // if the target point is reached, return true
        if (tx === sx && ty === sy) return true;
        // if the target point's x coordinate is greater than or equal to the starting point's x coordinate,
        // subtract the starting point's y coordinate from the target point's y coordinate
        if (tx >= sx) {
            ty -= sx;
        } else {
        // if the target point's y coordinate is greater than or equal to the starting point's y coordinate,
        // subtract the starting point's x coordinate from the target point's x coordinate
            tx -= sy;
        }
    }
    // if the target point is not reached after iterating through every possible point, return false
    return false;
};

int reachingPoints(int sx, int sy, int tx, int ty) 
{
    // Base cases 
    if (tx < sx || ty < sy) 
        return 0; 
    if (sx == tx && sy == ty) 
        return 1; 
  
    // Because we need to move either right or down 
    if (sx == tx) 
        return (ty - sy) % sx == 0; 
    if (sy == ty) 
        return (tx - sx) % sy == 0; 
  
    // Recursive calls for right movement and downward movement 
    return reachingPoints(sx, sy, tx - ty, ty) ||  
           reachingPoints(sx, sy, tx, ty - tx); 
}

using System; 

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