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: [3]

💡 Note: Ball passes: 1→2→1. Friends 1,2 receive the ball. Friend 3 never gets it.

Constraints

1 ≤ n ≤ 50
1 ≤ k ≤ n

Visualization

Tap to expand

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

✓ Optimized Simulation

⏱️ Time: O(n) Space: O(n)

This is essentially the same approach but with some micro-optimizations like using arrays instead of sets where possible and avoiding unnecessary operations. The core algorithm remains the same simulation.

Simulation with Set

⏱️ Time: O(n) Space: O(n)

We simulate the exact game by starting with friend 1, then passing the ball according to the rules (k steps, 2k steps, 3k steps, etc.) until someone receives it twice. We use a set to track who has received the ball.

Optimized Simulation — Algorithm Steps

Step 1: Use boolean array to track received friends
Step 2: Simulate game with optimized position calculation
Step 3: Early termination when repeat found
Step 4: Collect losers in single pass

Visualization

Tap to expand

Step-by-Step Walkthrough

Setup

Boolean array to track received friends

Optimized Movement

Efficient position calculation with modulo

Collect

Single pass to find all losers

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;
        int steps = (turn * k) % n;
        current = current + steps;
        if (current > n) current -= n;
        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)

Still need to visit each friend at most once before finding repeat

✓ Linear Growth

Space Complexity

O(n)

Boolean array of size n to track who received 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

Find the Losers of the Circular Game - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler