#2543

Hard

LeetCode Problem Workspace

Check if Point Is Reachable

Determine if a target point is reachable from (1,1) using math-based moves following number theory rules efficiently.

Problem Statement

You are on an infinite grid at position (1,1). Each move allows you to transform your current position using specific rules based on number theory.

Given integers targetX and targetY, determine whether it is possible to reach the point (targetX, targetY) from (1,1) using any sequence of valid steps, returning true if possible and false otherwise.

Examples

Example 1

Input: targetX = 6, targetY = 9

Output: false

It is impossible to reach (6,9) from (1,1) using any sequence of moves, so false is returned.

Example 2

Input: targetX = 4, targetY = 7

Output: true

You can follow the path (1,1) -> (1,2) -> (1,4) -> (1,8) -> (1,7) -> (2,7) -> (4,7).

Constraints

1 <= targetX, targetY <= 109

Solution Approach

Reverse Traversal Using Number Theory

Work backwards from (targetX, targetY) to (1,1). If targetX is even, consider x/2, if targetY is even, consider y/2. Otherwise, subtract the smaller coordinate from the larger. Continue until you reach (1,1) or the coordinates become invalid.

Recursive or Iterative Check

Implement a recursive function or a loop that applies the reverse rules repeatedly. Ensure proper handling of stopping conditions and avoid infinite loops. This approach captures all possible sequences that could lead to (1,1).

Mathematical Validation

Use properties of GCD and parity to quickly validate impossible targets. If at any point the coordinates cannot reduce to (1,1) due to number-theory constraints, immediately return false to save computation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time and space complexity depend on how many reverse operations are applied. In the worst case, each step roughly halves a coordinate or subtracts values, giving logarithmic bounds, but exact performance varies with the input pattern.

What Interviewers Usually Probe

Look for the candidate attempting a reverse approach from target to origin.
Watch for correct handling of even and odd coordinate cases using number theory.
Assess whether the solution avoids unnecessary recursion and infinite loops.

Common Pitfalls or Variants

Common pitfalls

Trying only forward moves from (1,1) leads to excessive search space.
Ignoring parity and GCD constraints can cause incorrect true results.
Failing to stop recursion or loops when coordinates cannot reduce causes infinite computation.

Follow-up variants

Determine reachability on a grid where moves allow multiplication or division by 3 instead of 2.
Find the minimum number of steps required to reach a target point using the same move rules.
Check reachability with additional diagonal moves combining x and y increments.

FAQ

What is the main strategy to solve Check if Point Is Reachable?

The main strategy is to work backwards from the target coordinates using allowed reverse operations until reaching (1,1) or an invalid state.

Why do we check parity and even/odd conditions in this problem?

Parity and even/odd checks help determine which reverse moves are valid and prevent impossible sequences that cannot reach (1,1).

Can a forward-only approach from (1,1) work efficiently?

No, forward-only simulation leads to exponential growth of possibilities, making the solution inefficient for large coordinates.

How does number theory guide move selection in this problem?

Number theory allows reduction rules like dividing even coordinates and subtracting smaller from larger, ensuring only valid sequences toward (1,1) are considered.

What are common mistakes when implementing this solution?

Common mistakes include ignoring reverse moves, not handling even/odd cases, and missing stopping conditions, which can lead to incorrect results or infinite loops.

terminal

Solution

Solution 1: Mathematics

We notice that the first two types of moves do not change the greatest common divisor (gcd) of the horizontal and vertical coordinates, while the last two types of moves can multiply the gcd of the horizontal and vertical coordinates by a power of $2$. In other words, the final gcd of the horizontal and vertical coordinates must be a power of $2$. If the gcd is not a power of $2$, then it is impossible to reach.

1

2

3

4

class Solution:
    def isReachable(self, targetX: int, targetY: int) -> bool:
        x = gcd(targetX, targetY)
        return x & (x - 1) == 0

Continue Practicing

#2523 closest prime numbers in range #2521 distinct prime factors of product of array #2513 minimize the maximum of two arrays