How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Hackerrank.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Hackerrank during technical interviews.

Find Final Ball Holder | Hackerrank Coding Question

Find Final Ball Holder

Company: Hackerrank

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given an array `receiver` of length `n`, where friends are numbered from `1` to `n`. If friend `i` currently holds the ball, then after one second they pass it to friend `receiver[i - 1]`. Initially, at time `0`, friend `1` has the ball. Given a non-negative integer `k`, return the friend number that holds the ball after exactly `k` seconds. Assume `k` can be very large, so a solution that simulates every second may be too slow. Example: - `receiver = [2, 4, 5, 3, 1]` - `k = 6` Ball movement: `1 -> 2 -> 4 -> 5 -> 3 -> 1 -> 2` Return `2`.

Quick Answer: This question evaluates understanding of functional graphs, cycle detection, and handling large-step transitions in deterministic mappings where repeated state updates occur.

You are given an array `receiver` of length `n`, where friends are numbered from `1` to `n`. If friend `i` currently holds the ball, then after one second they pass it to friend `receiver[i - 1]`. Initially, at time `0`, friend `1` has the ball. Given a non-negative integer `k`, return the friend number that holds the ball after exactly `k` seconds. Because `k` can be very large, a solution that simulates every second may be too slow. Example: - `receiver = [2, 4, 5, 3, 1]` - `k = 6` Ball movement: `1 -> 2 -> 4 -> 3 -> 5 -> 1 -> 2` So the answer is `2`.

Constraints

1 <= n == len(receiver) <= 2 * 10^5
1 <= receiver[i] <= n
0 <= k <= 10^18
Each friend passes the ball to exactly one friend

Examples

Input: ([2, 4, 5, 3, 1], 6)

Expected Output: 2

Explanation: The path is 1 -> 2 -> 4 -> 3 -> 5 -> 1 -> 2, so after 6 seconds friend 2 has the ball.

Input: ([1], 0)

Expected Output: 1

Explanation: At time 0, friend 1 already has the ball.

Input: ([2, 3, 4, 5, 3], 10)

Expected Output: 5

Explanation: The path is 1 -> 2 -> 3 -> 4 -> 5 -> 3 -> 4 -> 5 -> 3 -> 4 -> 5. After 10 seconds the ball is at friend 5.

Input: ([2, 1, 4, 3], 1000000000001)

Expected Output: 2

Explanation: Starting from friend 1, the ball alternates between 1 and 2. Since k is odd, friend 2 holds the ball.

Input: ([2, 3, 3], 100)

Expected Output: 3

Explanation: The path is 1 -> 2 -> 3, and then friend 3 keeps the ball forever because receiver[2] = 3.

Hints

If you record the first time each friend is visited, you can detect when the ball movement starts repeating.
Once you find a cycle, you do not need to simulate all remaining seconds; use modular arithmetic to jump to the final position.

Quick Overview

This question evaluates understanding of functional graphs, cycle detection, and handling large-step transitions in deterministic mappings where repeated state updates occur.