Find the Losers of the Circular Game — Easy Problem & Solution

Problem statement

n friends sit in a circle, numbered 1 to n clockwise. Friend 1 starts with a ball and passes it k steps clockwise. The receiver passes it 2k steps, the next 3k steps, and so on.

The game ends when someone receives the ball for the second time. Return the friends who never received it, in increasing order.

Example 1

Input: n = 5, k = 2
Output: [4,5]
Explanation: The ball visits 1 → 3 → 2 → 3, so 4 and 5 never touch it.

Example 2

Input: n = 4, k = 4
Output: [2,3,4]
Explanation: Every pass returns to friend 1.

Example 3

Input: n = 2, k = 1
Output: []
Explanation: Both friends receive the ball.

Constraints

• 1 <= k <= n <= 50

How to solve Find the Losers of the Circular Game

Direct simulation. Mark each position as it receives the ball; on turn t, move t · k steps clockwise with modular arithmetic. The first repeat ends the game, and the unmarked positions are the losers.

Approach

1. Track a seen flag per friend, starting at position 1 and turn 1.
2. While the current position is unseen, mark it and move to ((pos - 1 + turn · k) mod n) + 1, incrementing the turn.
3. Collect the unmarked friends in increasing order.

Why it works

The -1 … +1 dance is what makes 1-based seating work with a 0-based modulo — doing the modulo directly on 1-based positions lands on 0, which is nobody. The game is guaranteed to end because there are only n positions, so a repeat must occur within n passes.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• The step size grows each turn: it is t · k, not a constant k.
• Positions are 1-based; a naive pos % n produces 0.
• The result may legitimately be empty.

Reference solution

Python

from typing import List

def circularGameLosers(n: int, k: int) -> List[int]:
    seen = [False] * (n + 1)
    pos, turn = 1, 1
    while not seen[pos]:
        seen[pos] = True
        pos = (pos - 1 + turn * k) % n + 1
        turn += 1
    return [i for i in range(1, n + 1) if not seen[i]]

JavaScript

var circularGameLosers = function(n, k) {
    var seen = [], i;
    for (i = 0; i <= n; i++) seen.push(false);
    var pos = 1, turn = 1;
    while (!seen[pos]) {
        seen[pos] = true;
        pos = ((pos - 1 + turn * k) % n) + 1;
        turn++;
    }
    var losers = [];
    for (i = 1; i <= n; i++) if (!seen[i]) losers.push(i);
    return losers;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy
• Most Frequent Even Element Easy