Find the Winner of the Circular Game - Practice Coding Problems

Find the Winner of the Circular Game - Problem

Array Math Recursion Queue Simulation Medium

There are n friends sitting in a circle, numbered from 1 to n in clockwise order. The game follows these rules:

Start at friend 1
Count k friends clockwise (including the current friend)
The k-th friend is eliminated and leaves the circle
Continue from the next friend clockwise until only one remains

Given n friends and counting number k, return the position of the winner (the last remaining friend).

Input & Output

Example 1 — Basic Case

$ Input: n = 5, k = 2

› Output: 3

💡 Note: Start at friend 1, count 2 friends clockwise (1→2), eliminate friend 2. Continue from friend 3, count 2 (3→4), eliminate friend 4. Process continues until friend 3 remains as winner.

Example 2 — Single Friend

$ Input: n = 1, k = 1

› Output: 1

💡 Note: Only one friend in the circle, so friend 1 automatically wins the game.

Example 3 — Large Step Size

$ Input: n = 6, k = 5

› Output: 1

💡 Note: With 6 friends and k=5, we count 5 positions each time. The elimination pattern results in friend 1 being the last remaining.

Constraints

1 ≤ n ≤ 500
1 ≤ k ≤ n

Visualization

Tap to expand

Understanding the Visualization

Setup

n friends arranged in circle, numbered 1 to n

Eliminate

Count k friends clockwise, eliminate the k-th friend

Winner

Last remaining friend wins the game

Key Takeaway

🎯 Key Insight: This classic Josephus problem can be solved optimally using the mathematical recurrence relation J(n,k) = (J(n-1,k) + k) % n

Asked in

G Google 15 M Microsoft 12 a Amazon 10 f Facebook 8

The key insight is recognizing this as the classic Josephus problem. While simulation works, the optimal approach uses the mathematical Josephus formula: J(n,k) = (J(n-1,k) + k) % n. Best approach achieves Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Queue-Based Simulation	O(nk)	O(n)	Use a queue to efficiently simulate the circular elimination process
Josephus Formula	O(n)	O(1)	Apply the mathematical Josephus formula for O(n) solution
Simulation with Array	O(n²)	O(n)	Simulate the elimination process using an array to track remaining friends

Queue-Based Simulation — Algorithm Steps

Create queue with friends 1 to n
For each elimination: rotate k-1 times, then remove front
Continue until queue has one element
Return the remaining friend

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Queue

Queue with all friends [1,2,3,4,5]

Rotate & Eliminate

Rotate k-1 times, remove front element

Winner Found

Last remaining friend in queue

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

int solution(int n, int k) {
    int* queue = (int*)malloc(n * sizeof(int));
    int front = 0, rear = 0, size = 0;
    
    // Initialize queue
    for (int i = 1; i <= n; i++) {
        queue[rear] = i;
        rear = (rear + 1) % n;
        size++;
    }
    
    while (size > 1) {
        // Rotate k-1 times
        for (int i = 0; i < k - 1; i++) {
            queue[rear] = queue[front];
            front = (front + 1) % n;
            rear = (rear + 1) % n;
        }
        // Remove the k-th friend
        front = (front + 1) % n;
        size--;
    }
    
    int result = queue[front];
    free(queue);
    return result;
}

int main() {
    int n, k;
    scanf("%d", &n);
    scanf("%d", &k);
    printf("%d\n", solution(n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(nk)

n eliminations, each requiring k-1 rotations of the queue

✓ Linear Growth

Space Complexity

O(n)

Queue stores all n friends

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

889 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Queue-Based Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler