Find the Losers of the Circular Game - Practice Coding Problems

Find the Losers of the Circular Game - Problem

There are n friends that are playing a game. The friends are sitting in a circle and are numbered from 1 to n in clockwise order. More formally, moving clockwise from the ith friend brings you to the (i+1)th friend for 1 <= i < n, and moving clockwise from the nth friend brings you to the 1st friend.

The rules of the game are as follows:

1st friend receives the ball.
After that, 1st friend passes it to the friend who is k steps away from them in the clockwise direction.
After that, the friend who receives the ball should pass it to the friend who is 2 * k steps away from them in the clockwise direction.
After that, the friend who receives the ball should pass it to the friend who is 3 * k steps away from them in the clockwise direction, and so on and so forth.

In other words, on the ith turn, the friend holding the ball should pass it to the friend who is i * k steps away from them in the clockwise direction.

The game is finished when some friend receives the ball for the second time.

The losers of the game are friends who did not receive the ball in the entire game.

Given the number of friends, n, and an integer k, return the array answer, which contains the losers of the game in the ascending order.

Input & Output

Example 1 — Basic Case

$ Input: n = 5, k = 2

› Output: [4,5]

💡 Note: Ball passes: 1→3→2→1. Friends 1,2,3 received ball. Friends 4,5 never got it.

Example 2 — Smaller Circle

$ Input: n = 4, k = 4

› Output: [2,3,4]

💡 Note: Ball passes: 1→1 (4 steps in circle of 4 returns to 1). Only friend 1 gets the ball.

Example 3 — All Get Ball

$ Input: n = 3, k = 1

› Output: []

💡 Note: Ball passes: 1→2→3→1. All friends receive the ball, so no losers.

Constraints

1 ≤ n ≤ 50
1 ≤ k ≤ n

Visualization

Tap to expand

Understanding the Visualization

Input

n=5 friends in circle, k=2 step size

Process

Simulate ball passing until someone gets it twice

Output

Friends who never received the ball

Key Takeaway

🎯 Key Insight: Simulate the game rules exactly and track which friends never receive the ball using a set or boolean array

Asked in

a Amazon 15 M Microsoft 10

The key insight is to simulate the exact game rules by tracking ball positions and detecting when someone receives it twice. Best approach is simulation with set/array tracking to identify who never gets the ball. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Simulation with Set	O(n)	O(n)	Simulate the game step by step, tracking who receives the ball
Optimized Simulation	O(n)	O(n)	Same simulation but with early termination optimizations

Simulation with Set — Algorithm Steps

Step 1: Initialize a set to track who received the ball
Step 2: Start with friend 1 and simulate ball passing
Step 3: For each turn i, move i*k steps clockwise
Step 4: Stop when someone receives the ball twice
Step 5: Return friends not in the set

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with friend 1, empty set

Simulate

Pass ball according to rules until repeat

Find Losers

Return friends not in received set

Code -

solution.c — C

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

int* solution(int n, int k, int* returnSize) {
    bool* received = (bool*)calloc(n + 1, sizeof(bool));
    int current = 1;
    int turn = 1;
    
    while (!received[current]) {
        received[current] = true;
        current = (current - 1 + turn * k) % n + 1;
        turn++;
    }
    
    int* losers = (int*)malloc(n * sizeof(int));
    *returnSize = 0;
    
    for (int i = 1; i <= n; i++) {
        if (!received[i]) {
            losers[(*returnSize)++] = i;
        }
    }
    
    free(received);
    return losers;
}

int main() {
    int n, k;
    scanf("%d", &n);
    scanf("%d", &k);
    
    int returnSize;
    int* result = solution(n, k, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

In worst case, we visit each friend once before finding a repeat

✓ Linear Growth

Space Complexity

O(n)

Set stores up to n friends who received the ball

⚡ Linearithmic Space

12.0K Views

Medium Frequency

~15 min Avg. Time

450 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

Simulation with Set — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler