Skip to content

2682. Find the Losers of the Circular Game 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  vector<int> circularGameLosers(int n, int k) {
    vector<int> ans;
    vector<bool> seen(n);

    for (int friendIndex = 0, turn = 1; !seen[friendIndex];) {
      seen[friendIndex] = true;
      friendIndex += turn++ * k;
      friendIndex %= n;
    }

    for (int friendIndex = 0; friendIndex < n; ++friendIndex)
      if (!seen[friendIndex])
        ans.push_back(friendIndex + 1);

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public int[] circularGameLosers(int n, int k) {
    List<Integer> ans = new ArrayList<>();
    boolean[] seen = new boolean[n];

    for (int friendIndex = 0, turn = 1; !seen[friendIndex];) {
      seen[friendIndex] = true;
      friendIndex += turn++ * k;
      friendIndex %= n;
    }

    for (int friendIndex = 0; friendIndex < n; ++friendIndex)
      if (!seen[friendIndex])
        ans.add(friendIndex + 1);

    return ans.stream().mapToInt(Integer::intValue).toArray();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def circularGameLosers(self, n: int, k: int) -> List[int]:
    seen = [False] * n
    friendIndex = 0
    turn = 1

    while not seen[friendIndex]:
      seen[friendIndex] = True
      friendIndex += turn * k
      friendIndex %= n
      turn += 1

    return [friendIndex + 1
            for friendIndex in range(n)
            if not seen[friendIndex]]