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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Losers of the Circular Game

Difficulty: Easy

Problem Description

There are n friends that are playing a game in a circular arrangement. The 1st friend starts with the ball and passes it to the friend who is k steps away in a clockwise direction. The next friend will pass it to the friend who is 2 * k steps away, and so on. The game ends when a friend receives the ball for the second time. The task is to find the friends who never received the ball, referred to as "losers".

Key Insights

  • The friends are arranged in a circular manner, making it necessary to use modulo arithmetic to wrap around the indices.
  • The passing of the ball increases with each turn: the 1st pass is k steps, the 2nd pass is 2 * k steps, etc.
  • A set can be utilized to keep track of friends who have received the ball.
  • The game continues until a friend receives the ball for the second time.

Space and Time Complexity

Time Complexity: O(n) - The algorithm iterates through the friends and keeps track of who has received the ball. Space Complexity: O(n) - A set is used to track the friends who have received the ball.

Solution

To solve the problem, we can use a set to keep track of the friends who have received the ball. We start passing the ball from the 1st friend, using a loop that increments the steps based on the turn number (i.e., i * k). If a friend receives the ball for the second time, we stop the game. Finally, we can determine the losers by checking which friends are not in the set of friends who received the ball.

Code Solutions

def findLosers(n, k):
    seen = set()  # To keep track of friends who received the ball
    current = 0    # Start with the 1st friend (index 0)
    
    while current not in seen:
        seen.add(current)  # Mark the current friend as having received the ball
        current = (current + len(seen) * k) % n  # Calculate the next friend to receive the ball
    
    # List of losers are friends not in seen
    return sorted(set(range(1, n + 1)) - seen)

# Example Usage
print(findLosers(5, 2))  # Output: [4, 5]
print(findLosers(4, 4))  # Output: [2, 3, 4]
← Back to All Questions