Check if Point Is Reachable solution and explanation
6 more videos on this problem
Check if Point Is Reachable | Biweekly Contest 96 | LeetcodecodingMohan · 12:23 · 1K views
Check if Point Is Reachable || Leetcode 2543. || DSA || C++ code || Think then CodeThink then Code · 8:43 · 615 views
2543. Check if Point Is Reachable (Leetcode Hard)Programming Live with Larry · 24:33 · 591 views
2543. Check if Point Is Reachable | Leetcode Biweekly contest 96Tech Courses · 6:30 · 521 views
【每日一题】LeetCode 2543. Check if Point Is ReachableHuifeng Guan · 13:55 · 382 views
D. Check if Point is Reachable - LEETCODE BIWEEKLY CONTEST 96 (Code + Explanation in details)Joyjit Codes · 4:42 · 339 views
leetcode 2543. Check if Point Is Reachable - analyze the gcd prime factorsCode-Yao · 12:18 · 61 views
The problem
There exists an infinitely large grid. You are currently at point (1, 1), and you need to reach the point (targetX, targetY) using a finite number of steps.
In one step, you can move from point (x, y) to any one of the following points:
(x, y - x)(x - y, y)(2 * x, y)(x, 2 * y)
Given two integers targetX and targetY representing the X-coordinate and Y-coordinate of your final position, return true if you can reach the point from (1, 1) using some number of steps, and false otherwise.
Example 1:
Input: targetX = 6, targetY = 9 Output: false Explanation: 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 Explanation: You can follow the path (1,1) -> (1,2) -> (1,4) -> (1,8) -> (1,7) -> (2,7) -> (4,7).
Constraints:
1 <= targetX, targetY <= 109
Approach overview
Problem Overview: Starting from point (1,1), you can repeatedly transform the coordinates using operations that add one coordinate to the other or double one coordinate. Given (targetX, targetY), determine whether it is possible to reach that point. The challenge is recognizing how these operations affect the greatest common divisor of the coordinates.
Approach 1: Reverse Operations (O(log(max(x,y))) time, O(1) space)
Instead of constructing the path forward from (1,1), work backward from (targetX, targetY). The reverse of doubling is dividing by two when the coordinate is even, and the reverse of adding coordinates is subtracting the smaller value from the larger. Repeatedly apply these reductions: divide by 2 if possible, otherwise subtract the smaller coordinate from the larger. This gradually shrinks the pair until it either reaches (1,1) or becomes impossible to reduce further.
The key observation is that subtraction preserves the gcd(x, y), while dividing by 2 only removes factors of two. Because the numbers shrink quickly, the loop runs in logarithmic time. This approach mirrors the Euclidean algorithm and highlights how the allowed moves interact with math properties of the coordinates.
Approach 2: Recursive GCD-based Reduction (O(log n) time, O(1) space)
A stronger insight eliminates simulation entirely. Addition operations do not change the greatest common divisor of the coordinates, while doubling multiplies the gcd by 2. Since the starting point (1,1) has gcd = 1, any reachable point must have a gcd that is a power of two. If the gcd contained any odd factor greater than 1, no sequence of valid operations could produce it.
So the solution reduces to computing g = gcd(targetX, targetY). If g is a power of two, the point is reachable; otherwise it is not. Checking this condition is simple using the bit trick g & (g - 1) == 0. This approach relies on properties from number theory and the classic Euclidean algorithm.
This mathematical reduction is extremely efficient and avoids iterative coordinate manipulation entirely.
Recommended for interviews: The GCD-based approach. Interviewers expect you to recognize that the operations preserve gcd except for powers of two introduced by doubling. Showing the reverse-operations reasoning first demonstrates understanding of the transformation process, while deriving the gcd power-of-two condition shows deeper algorithmic insight.
Approach 1: Approach 1: Reverse Operations
This approach involves working backward from the target point `(targetX, targetY)` to the starting point `(1, 1)`. Consider the inverse operations of the allowed steps.
- For (x, y), the inverse of moving to `(x - y, y)` is `(x + y, y)`.
- The inverse of moving to `(x, y - x)` is `(x, x + y)`.
- The inverse of moving to `(2 * x, y)` is `(x / 2, y)` (if x is even).
- The inverse of moving to `(x, 2 * y)` is `(x, y / 2)` (if y is even).
Thus, you can start at `(targetX, targetY)` and repeatedly find the preceding points until you reach `(1, 1)` or determine it's impossible.
def isReachable(targetX: int, targetY: int) -> bool:
while targetX > 1 and targetY > 1:
if targetX > targetY:
targetX %= targetY
else:
targetY %= targetX
return (targetX == 1 and (targetY == 1 or targetY % targetX == 0)) or (targetY == 1 and (targetX == 1 or targetX % targetY == 0))public class Solution {
public boolean isReachable(int targetX, int targetY) {
while (targetX > 1 && targetY > 1) {
if (targetX > targetY) {
targetX %= targetY;
} else {
targetY %= targetX;
}
}
return (targetX == 1 && (targetY == 1 || targetY % targetX == 0)) || (targetY == 1 && (targetX == 1 || targetX % targetY == 0));
}
}#include <iostream>
bool isReachable(int targetX, int targetY) {
while (targetX > 1 && targetY > 1) {
if (targetX > targetY) {
targetX %= targetY;
} else {
targetY %= targetX;
}
}
return (targetX == 1 && (targetY == 1 || targetY % targetX == 0)) || (targetY == 1 && (targetX == 1 || targetX % targetY == 0));
}function isReachable(targetX, targetY) {
while (targetX > 1 && targetY > 1) {
if (targetX > targetY) {
targetX %= targetY;
} else {
targetY %= targetX;
}
}
return (targetX === 1 && (targetY === 1 || targetY % targetX === 0)) || (targetY === 1 && (targetX === 1 || targetX % targetY === 0));
}#include <stdbool.h>
bool isReachable(int targetX, int targetY) {
while (targetX > 1 && targetY > 1) {
if (targetX > targetY) {
targetX %= targetY;
} else {
targetY %= targetX;
}
}
return (targetX == 1 && (targetY == 1 || targetY % targetX == 0)) || (targetY == 1 && (targetX == 1 || targetX % targetY == 0));
}public class Solution {
public bool IsReachable(int targetX, int targetY) {
while (targetX > 1 && targetY > 1) {
if (targetX > targetY) {
targetX %= targetY;
} else {
targetY %= targetX;
}
}
return (targetX == 1 && (targetY == 1 || targetY % targetX == 0)) || (targetY == 1 && (targetX == 1 || targetX % targetY == 0));
}
}The Python solution uses the same logic structure, operating by reducing the larger of the two coordinates by modulo operation until one reduces to 1, and checking if the remainder corroborates an initial path possibility.
Time Complexity: O(log(max(targetX, targetY)))
Space Complexity: O(1)
Approach 2: Approach 2: Recursive GCD-based Reduction
Approach 2 uses the Greatest Common Divisor (GCD) property, based on the observation that valid steps only change the relative prime basis of points minimally.
By recursively determining the GCD of targetX and targetY, the task simplifies to checking if one coordinate could shrink to 1 provided it maintains divisibility by the other throughout the recursive checks.
import math
def isReachable(targetX: int, targetY: int) -> bool:
return math.gcd(targetX, targetY) == 1public class Solution {
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
public boolean isReachable(int targetX, int targetY) {
return gcd(targetX, targetY) == 1;
}
}#include <iostream>
#include <algorithm>
bool isReachable(int targetX, int targetY) {
return std::__gcd(targetX, targetY) == 1;
}function gcd(a, b) {
while (b !== 0) {
let temp = b;
b = a % b;
a = temp;
}
return a;
}
function isReachable(targetX, targetY) {
return gcd(targetX, targetY) === 1;
}#include <stdbool.h>
int gcd(int a, int b) {
while (b) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
bool isReachable(int targetX, int targetY) {
return gcd(targetX, targetY) == 1;
}using System;
public class Solution {
private int Gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
public bool IsReachable(int targetX, int targetY) {
return Gcd(targetX, targetY) == 1;
}
}Utilizing Python's built-in math function to determine the GCD, it authenticates the prime valuation indicating a possible returnable route from target conditions back to (1, 1).
Time Complexity: O(log(min(targetX, targetY))) due to the GCD calculation.
Space Complexity: O(1)
Approach 3: 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.
Next, we prove that any (x, y) that satisfies gcd(x, y)=2^k can be reached.
We reverse the direction of movement, that is, move from the end point back. Then (x, y) can move to (x, x+y), (x+y, y), (\frac{x}{2}, y), and (x, \frac{y}{2}).
As long as x or y is even, we divide it by 2 until both x and y are odd. At this point, if x neq y, without loss of generality, let x \gt y, then \frac{x+y}{2} \lt x. Since x+y is even, we can move from (x, y) to (x+y, y), and then to (\frac{x+y}{2}, y) through operations. That is to say, we can always make x and y continuously decrease. When the loop ends, if x=y=1, it means it can be reached.
The time complexity is O(log(min(targetX, targetY))), and the space complexity is O(1).
function isReachable(targetX: number, targetY: number): boolean {
const x = gcd(targetX, targetY);
return (x & (x - 1)) === 0;
}
function gcd(a: number, b: number): number {
return b == 0 ? a : gcd(b, a % b);
}func isReachable(targetX int, targetY int) bool {
x := gcd(targetX, targetY)
return x&(x-1) == 0
}
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Reverse Operations | Time Complexity: O(log(max(targetX, targetY))) |
| Approach 2: Recursive GCD-based Reduction | Time Complexity: O(log(min(targetX, targetY))) due to the GCD calculation. |
| Mathematics | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Reverse Operations | O(log(max(x,y))) | O(1) | When reasoning about the problem through simulation and understanding how operations reduce coordinates |
| GCD Power-of-Two Check | O(log n) | O(1) | Best approach for production or interviews; relies on number theory insight |
Frequently asked questions
Is Check if Point Is Reachable easy or hard?
The problem is labeled Hard because the optimal solution depends on recognizing a number theory property of gcd. Once the mathematical insight is identified, the implementation becomes very small and runs in O(log n) time.
Check if Point Is Reachable Python/Java solution
In Python or Java, compute gcd(targetX, targetY) using the built-in or standard Euclidean algorithm. Then check if the gcd is a power of two using the condition g & (g - 1) == 0. If true, return reachable; otherwise return false.
How to solve Check if Point Is Reachable in O(log n)?
Compute g = gcd(targetX, targetY). If g is a power of two, the point is reachable from (1,1); otherwise it is not. This works because allowed operations preserve gcd except when doubling introduces additional factors of two.
What is the best approach for Check if Point Is Reachable?
The optimal approach computes gcd(targetX, targetY) and checks whether the result is a power of two. Addition operations keep the gcd unchanged, while doubling multiplies it by 2. Since the start point (1,1) has gcd = 1, any reachable point must have a gcd equal to 2^k. This yields an O(log n) solution using the Euclidean algorithm.
Is Check if Point Is Reachable asked at Google/Amazon/Meta?
Problems involving gcd transformations, reverse operations, and number theory frequently appear in interviews at companies like Google, Amazon, and Meta. This question tests mathematical reasoning and the ability to reduce operations to a gcd property.
What data structure is used in Check if Point Is Reachable?
No complex data structure is required. The solution mainly relies on mathematical operations such as the Euclidean algorithm for computing gcd and a bitwise check to determine whether the gcd is a power of two.
What is the time complexity of Check if Point Is Reachable?
The optimal solution runs in O(log n) time because it relies on the Euclidean algorithm to compute gcd(targetX, targetY). The space complexity is O(1). A reverse-simulation approach that repeatedly subtracts or divides by two also runs in roughly logarithmic time.