Katkat
Back

Find Final Ball Holder

HackerRankSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to optimize repeated state transitions by identifying cycles in a functional graph or using modular arithmetic to jump through large steps.

Problem Statement

You are given n children standing in a circle, indexed from 0 to n-1. A ball is passed around the circle. Initially, the ball is at child 0. In each step i (where i starts at 1), the ball is passed to the person standing i positions clockwise from the current holder. If the ball reaches the end of the circle, it wraps around to the beginning.

Given the total number of children n and the total number of steps k, determine the index of the child holding the ball after exactly k steps.

Function Signature

def find_final_ball_holder(n: int, k: int) -> int:

Constraints

  • `1 1.
  • Step 2: Pass 2 positions. Ball moves 1 -> (1 + 2) % 5 = 3.
  • Output: 3

Example 2:

  • Input: n = 3, k = 3
  • Step 1: 0 -> 1
  • Step 2: 1 -> (1 + 2) % 3 = 0
  • Step 3: 0 -> (0 + 3) % 3 = 0
  • Output: 0

Edge Cases

  • k is very large relative to n.
  • n = 1 always results in index 0.

Hints

Hint 1

Notice that the position of the ball after `k` steps is the sum of integers from 1 to `k` modulo `n`.

Hint 2

Recall the formula for the sum of the first `k` integers: `sum = k * (k + 1) / 2`.

Hint 3

Since `k` is very large, compute the result as `(k * (k + 1) // 2) % n`.

Follow-up questions

  • What if the ball passing rule was not a simple increment, but a fixed permutation mapping `P` where `P[i]` is the next person to receive the ball?
  • How would you solve this if `k` were so large that you could not use the sum formula, but the movement was periodic with a shorter cycle than `k`?
  • How does the time complexity change if we move from an O(1) arithmetic approach to a cycle-detection approach?