FastPrepPlanets Queries from Planet One
Problem · Array

Planets Queries from Planet One

Learn this problem
● MediumAdyen logoAdyenFULLTIMEPHONE SCREEN

Problem statement

There are n planets numbered from 1 to n. Every planet has exactly one teleporter, possibly to itself. The array nextPlanet stores these destinations: the teleporter from planet i goes to nextPlanet[i - 1].

Every query starts on planet 1. For each value steps[j], follow exactly that many teleporters and return the planet reached. Return the answers in query order.

Function

planetsFromOne(nextPlanet: int[], steps: int[]) → int[]

Examples

Example 1

nextPlanet = [2,1,1,4]steps = [0,1,2,3,1000000000]return = [1,2,1,2,1]

The orbit from planet 1 alternates between 1 and 2. Zero steps stays at the start, and the billion-step query lands on planet 1.

Example 2

nextPlanet = [2,3,4,5,3]steps = [0,1,2,3,4,5,6]return = [1,2,3,4,5,3,4]

The route has a two-edge tail before entering the cycle 3 -> 4 -> 5 -> 3.

Example 3

nextPlanet = [1]steps = [0,1,999999999,1000000000]return = [1,1,1,1]

Planet 1 teleports to itself, so every query returns 1.

Constraints

  • 1 <= nextPlanet.length == n <= 2 * 10^5
  • 1 <= nextPlanet[i] <= n
  • 1 <= steps.length <= 2 * 10^5
  • 0 <= steps[j] <= 10^9

More Adyen problems

drafts saved locally
public int[] planetsFromOne(int[] nextPlanet, int[] steps) {
    // write your code here
}
nextPlanet[2,1,1,4]
steps[0,1,2,3,1000000000]
expected[1,2,1,2,1]
checking account