Reach a Cell With Sum Moves
Updated
Problem statement
You start at cell (1, 1) of an infinite grid and want to reach cell (m, n). From a cell (x, y) you can make one of two moves:
- An X move goes to
(x + y, y). - A Y move goes to
(x, x + y).
If (m, n) can be reached, return the shortest path to it written as blocks. Each block is a move letter followed by how many times that move is made in a row, and two neighboring blocks never use the same letter. For example, "Y2X1" means two Y moves and then one X move.
If (m, n) is (1, 1), no moves are needed, so return the empty string "". If (m, n) cannot be reached, return "NO".
At most one path leads to any cell, so the answer is always unique.
Function
findSumMovePath(m: int, n: int) → StringExamples
Example 1
m = 3n = 2return = "Y1X1"Work backward from (3, 2). Since 3 > 2, the last move was an X move from (1, 2). Since 1 < 2, the move before it was a Y move from (1, 1).
So the path is (1, 1) → (1, 2) → (3, 2): one Y move, then one X move.
Example 2
m = 5n = 13return = "X1Y1X1Y2"The path is (1, 1) → (2, 1) → (2, 3) → (5, 3) → (5, 8) → (5, 13). The moves are X, Y, X, Y, Y. The last two Y moves form one block, so the answer is "X1Y1X1Y2".
Example 3
m = 4n = 6return = "NO"Every move keeps the greatest common divisor of the two numbers the same, and (1, 1) has greatest common divisor 1. Cell (4, 6) has greatest common divisor 2, so it cannot be reached.
Constraints
1 <= m, n <= 10^7
More Nutanix Onsite Interview questions
- Design Hit CounterONSITE INTERVIEW · Seen Oct 2026
- Peak Process MemoryONSITE INTERVIEW · Seen Aug 2026
- Minimum Operations to Transform ArrayONSITE INTERVIEW · Seen Jun 2026
- Count Connected Components in an Undirected GraphONSITE INTERVIEW · Seen Aug 2025
- LRU CacheONSITE INTERVIEW · Seen Aug 2025
- Running Median of a Multilevel Linked List in Level OrderONSITE INTERVIEW · Seen Aug 2025
- Custom Array IteratorONSITE INTERVIEW · Seen Dec 2024
- Collapse Runs of Repeated CharactersONSITE INTERVIEW · Seen Nov 2022
- Anagram Words in a SentenceONSITE INTERVIEW · Seen Apr 2022
- Sudoku SolverONSITE INTERVIEW · Seen Feb 2022
Similar questions at other companies
- Babysitter Quote with Hourly RatesUpstart · ONSITE INTERVIEWUpstart interview questions
- Expected Value of Modified DiceJane Street · ONSITE INTERVIEWJane Street interview questions
- Fractional Share Inventory FlatteningRobinhood · PHONE SCREEN · ONSITE INTERVIEWRobinhood interview questions
- Reservoir Sampling with Recorded DrawsMeta · ONSITE INTERVIEWMeta interview questions
- Group-Relative Policy AdvantagesAmazon · ONSITE INTERVIEW
- Reservoir Sampling with Recorded DrawsStackAdapt · ONSITE INTERVIEWStackAdapt interview questions
- Iterate Canonical IPv6 AddressesOpenAI · ONSITE INTERVIEWOpenAI interview questions
- Nth Staged License PlateGoogle · ONSITE INTERVIEWGoogle interview questions
- UCB1 Multi-Armed Bandit TraceWayfair · ONSITE INTERVIEWWayfair interview questions
- Rasterize a Circle with Integer PixelsPure Storage · ONSITE INTERVIEWPure Storage interview questions