FastPrep
Problem · Graph

Reaching Points with Perfect-Square Obstacles

Learn this problem
● MediumIMC logoIMCFULLTIMEOA

Problem statement

A bot starts at the positive integer coordinate (startX, startY) and wants to reach (targetX, targetY). A positive constant c is fixed for the entire journey.

From a coordinate (x, y), the bot may make exactly one of these moves:

  1. Move to (x + y, y).
  2. Move to (x, x + y).
  3. Move to (x + c, y + c).

A coordinate is forbidden when x + y is a perfect square. The bot may never occupy a forbidden coordinate. This rule also applies to the starting and target coordinates.

Return "Yes" if a sequence of legal moves reaches the target. Otherwise, return "No".

Function

canReach(c: int, startX: int, startY: int, targetX: int, targetY: int) → String

Examples

Example 1

c = 1startX = 2startY = 1targetX = 3targetY = 5return = "Yes"

The bot can move from (2, 1) to (3, 2) using the third move, then to (3, 5) using the second move. Neither visited sum is a perfect square.

Example 2

c = 2startX = 2startY = 7targetX = 10targetY = 12return = "No"

The starting sum is 2 + 7 = 9, a perfect square, so no path is allowed.

Constraints

  • 1 <= c, startX, startY, targetX, targetY <= 1000
  • Every move strictly increases at least one coordinate.
  • If either endpoint's coordinate sum is a perfect square, the answer is "No".

More IMC problems

drafts saved locally
class Solution {
    public String canReach(int c, int startX, int startY,
                           int targetX, int targetY) {
        // Write your code here.
        return "No";
    }
}
c1
startX2
startY1
targetX3
targetY5
expected"Yes"
checking account