Reaching Points - Practice Coding Problems

Reaching Points - Problem

Math Hard

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

Input & Output

Example 1 — Reachable Target

$ Input: sx = 1, sy = 1, tx = 3, ty = 5

› Output: true

💡 Note: Path exists: (1,1) → (1,2) → (3,2) → (3,5). We can apply operations (1,1+1)=(1,2), then (1+2,2)=(3,2), then (3,3+2)=(3,5).

Example 2 — Unreachable Target

$ Input: sx = 1, sy = 1, tx = 2, ty = 2

› Output: false

💡 Note: From (1,1) we can only reach (1,2) or (2,1), but never (2,2). Both coordinates cannot increase simultaneously.

Example 3 — Same Point

$ Input: sx = 1, sy = 1, tx = 1, ty = 1

› Output: true

💡 Note: Source and target are the same point, so no operations needed.

Constraints

1 ≤ sx, sy, tx, ty ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Source (sx,sy) and target (tx,ty) coordinates

Process

Apply operations (x,x+y) or (x+y,y) to reach target

Output

Return true if target is reachable, false otherwise

Key Takeaway

🎯 Key Insight: Working backwards with modulo operations is exponentially faster than forward exploration

Asked in

G Google 15 f Facebook 8

The key insight is to work backwards from the target using mathematical reduction rather than forward exploration. The reverse mathematical approach uses modulo operations to efficiently reduce coordinates, achieving O(log(max(tx, ty))) time complexity instead of exponential forward search.

Common Approaches

Approach	Time	Space	Notes
✓ Forward BFS	O(2^(tx+ty))	O(2^(tx+ty))	Try all possible forward moves using BFS until reaching target
Reverse Mathematical Reduction	O(log(max(tx, ty)))	O(1)	Work backwards from target using subtraction and modulo operations

Forward BFS — Algorithm Steps

Start with queue containing (sx, sy)
For each point, generate two new points: (x, x+y) and (x+y, y)
Continue until target found or queue empty

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin at (sx, sy)

Expand

Generate (x, x+y) and (x+y, y) for each point

Continue until target found or no more moves

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

bool solution(int sx, int sy, int tx, int ty) {
    if (sx == tx && sy == ty) {
        return true;
    }
    
    // For simplicity, use a limit to avoid infinite loops
    // This is a simplified version that works for small inputs
    int queue[10000][2];
    int front = 0, rear = 0;
    
    queue[rear][0] = sx;
    queue[rear][1] = sy;
    rear++;
    
    while (front < rear && rear < 10000) {
        int x = queue[front][0];
        int y = queue[front][1];
        front++;
        
        int nextPoints[2][2] = {{x, x + y}, {x + y, y}};
        
        for (int i = 0; i < 2; i++) {
            int nx = nextPoints[i][0];
            int ny = nextPoints[i][1];
            
            if (nx == tx && ny == ty) {
                return true;
            }
            
            if (nx > tx || ny > ty || nx < 0 || ny < 0) {
                continue;
            }
            
            queue[rear][0] = nx;
            queue[rear][1] = ny;
            rear++;
        }
    }
    
    return false;
}

int main() {
    int sx, sy, tx, ty;
    scanf("%d", &sx);
    scanf("%d", &sy);
    scanf("%d", &tx);
    scanf("%d", &ty);
    
    bool result = solution(sx, sy, tx, ty);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^(tx+ty))

Each step can branch into 2 possibilities, leading to exponential growth

✓ Linear Growth

Space Complexity

O(2^(tx+ty))

BFS queue can store exponentially many intermediate points

✓ Linear Space

28.0K Views

Medium Frequency

~25 min Avg. Time

842 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Forward BFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler