algoadvance

Leetcode 3178. Find the Child Who Has the Ball After K Seconds

Problem Statement

You are given a list of n children who are playing a game. In this game, there is a ball that starts with the first child initially. The children pass the ball to the next child one by one until they reach the last child, after which the ball is again passed to the first child. This process continues indefinitely. You are required to determine which child has the ball after k seconds. The list of children is numbered starting from 0 to n-1.

Constraints:

Clarifying Questions

  1. Is there a specific starting position, or is it always the first child (index 0)?
    • The problem statement implies the ball always starts with the first child (index 0).
  2. Do the children pass the ball exactly every second?
    • Yes, each child passes the ball to the next child every second.

Strategy

  1. Simulate the Ball Passing:
    • Since the children are arranged in a circle, you can use modular arithmetic to determine the child with the ball after k seconds.
    • Find the child by computing k % n.
  2. Modulo Operation:
    • If the ball starts with the first child (index 0), then after k seconds, the position of the ball will be (0 + k) % n, where n is the total number of children.
    • The result of this modulo operation will give the index of the child holding the ball.

Code

Here’s the C++ code solving the problem:

#include <iostream>

int findChildWithBall(int n, int k) {
    // Compute the child who has the ball after k seconds
    return k % n;
}

int main() {
    int n, k;
    std::cout << "Enter number of children and seconds respectively: ";
    std::cin >> n >> k;

    int result = findChildWithBall(n, k);
    std::cout << "The child with the ball after " << k << " seconds is: " << result << std::endl;

    return 0;
}

Time Complexity

This implementation efficiently computes the index of the child holding the ball after k seconds, handling large values of n and k effectively due to the use of simple arithmetic operations.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI