FastPrep
Problem

Ball Passing at Time K

Learn this problem
HackerRank logoHackerRankFULLTIMEPHONE SCREEN

Problem statement

There are n friends numbered from 1 to n. You are given an array throwsTo, where throwsTo[i - 1] is the friend who receives the ball whenever friend i throws it.

Time is 1-indexed. At time 1, before any throws happen, friend 1 is holding the ball. To move from time t to time t + 1, the current holder throws the ball once to the friend indicated by throwsTo. Return the friend holding the ball at time k.

Equivalently, when answering time k, exactly k - 1 throws have occurred. Do not interpret k as the number of throws.

Function

friendHoldingBall(n: int, throwsTo: int[], k: long) → int

Examples

Example 1

n = 6throwsTo = [2,3,4,5,3,6]k = 10return = 4

At time 1, friend 1 has the ball. After each throw, the holders at times 1 through 10 are 1, 2, 3, 4, 5, 3, 4, 5, 3, 4. Therefore at time 10, after 9 throws, friend 4 holds the ball.

Example 2

n = 3throwsTo = [2,3,1]k = 1return = 1

At time 1, no throw has happened yet, so the initial holder friend 1 is returned.

Example 3

n = 4throwsTo = [2,2,4,3]k = 5return = 2

Friend 1 throws to friend 2, and friend 2 throws to themself, so friend 2 holds the ball at every time after 1.

Constraints

  • n == throwsTo.length
  • 1 <= n <= 2 * 10^5
  • 1 <= throwsTo[i] <= n
  • 1 <= k <= 10^18

More HackerRank problems

drafts saved locally
public int friendHoldingBall(int n, int[] throwsTo, long k) {
  // write your code here
}
n6
throwsTo[2,3,4,5,3,6]
k10
expected4
checking account