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 Winner of the Circular Game

Number: 1951

Difficulty: Medium

Paid? No

Companies: Goldman Sachs, Bloomberg, Google, Amazon, Meta, Walmart Labs, Accenture, Zoho, Microsoft, Yahoo

Problem Description

Given n friends sitting in a circle numbered from 1 to n, repeatedly eliminate one friend by counting k friends clockwise (including the starting friend) until only one friend remains. The task is to determine the winner of this circular elimination game.

Key Insights

  • The problem is a variation of the Josephus Problem.
  • A recurrence relation exists: f(1, k) = 0 and f(n, k) = (f(n - 1, k) + k) mod n.
  • The final answer must be adjusted to 1-indexed by adding 1 to the result.
  • The mathematical recurrence yields an O(n) time solution with O(1) space.
  • While simulation using a list or queue can solve the problem, it may be less efficient.

Space and Time Complexity

Time Complexity: O(n) using the mathematical recurrence. Space Complexity: O(1) as it only requires a few variables.

Solution

The optimal solution leverages the mathematical recurrence relation of the Josephus problem. The recurrence relation is defined as:

  • Base case: When there is only one friend, the winning index is 0.
  • Recurrence: For a circle of size n, the new winning index can be computed by (previous winner + k) mod n. After computing the solution using zero-based indexing, add 1 to convert it to one-based indexing.

We maintain a running winner position and update it as we iterate from 2 to n. This approach requires constant space and runs in linear time.

Code Solutions

# Python implementation for finding the winner in the circular game

def findWinner(n, k):
    # Initialize winner to 0 for the base case of 1 friend (0-indexed)
    winner = 0
    # Process from 2 friends to n friends
    for i in range(2, n + 1):
        # Update winner index based on recurrence relation
        winner = (winner + k) % i
    # Convert the 0-indexed winner to 1-indexed result
    return winner + 1

# Example usage:
n = 5
k = 2
print(findWinner(n, k))  # Expected output: 3
← Back to All Questions