We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Losers of the Circular Game

Number: 2791

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

There are n friends sitting in a circle, numbered 1 to n in clockwise order. The game starts with the 1st friend holding the ball. On the iᵗʰ turn, the friend with the ball passes it to the friend who is i * k steps away in the clockwise direction (using wrap-around via modulo arithmetic). The game stops as soon as a friend receives the ball for the second time. Losers are the friends who never received the ball during the game. Return the list of losers in ascending order.

Key Insights

  • The ball is passed in increments of k: k steps on the 1st pass, 2*k steps on the 2nd, and so on.
  • Modulo arithmetic is used to handle wrap-around in the circular arrangement.
  • A visited tracking mechanism (set or list) can help determine when a friend receives the ball for the second time.
  • The losers are those friends that were never visited during the simulation.

Space and Time Complexity

Time Complexity: O(n) - The simulation will visit at most n friends before a repeat occurs. Space Complexity: O(n) - We use an extra storage (list/array) of size n to track visited friends.

Solution

We solve the problem by simulating the ball passing process. Starting with friend 1, we maintain an array (or similar structure) to record which friends have received the ball. On each turn, we calculate the next friend using the current index plus the product of the current step count and k, modulo n. The simulation stops when a friend already marked as visited receives the ball again. Finally, we compile a list of all friends who never received the ball (losers) and return them in ascending order.

Code Solutions

Below are code implementations in Python, JavaScript, C++, and Java with line-by-line comments.

# Python solution
def circularGameLosers(n: int, k: int) -> list:
    # Create an array to track if a friend has received the ball (index 0 corresponds to friend 1)
    visited = [False] * n
    current = 0  # starting with friend 1 (index 0)
    step = 1     # turn counter starts at 1
    # Simulate the game until a friend receives the ball for the second time
    while not visited[current]:
        visited[current] = True  # mark the current friend as visited
        # Calculate the next friend index using modulo arithmetic.
        current = (current + step * k) % n
        step += 1  # increment turn for the next pass
    # Gather the losers, i.e., friends who never received the ball.
    losers = [i + 1 for i in range(n) if not visited[i]]
    return losers

# Example usage:
print(circularGameLosers(5, 2))  # Expected output: [4, 5]
← Back to All Questions