This approach simulates the game using a list (or array) to represent the friends. We start from the first friend and iteratively remove the k-th friend (considering the wrap around for the circle) until only one friend remains. The advantage of this method is its simplicity and straightforwardness, although it might not be the most efficient solution.
Steps:
Time Complexity: O(n^2), as each friend removal involves an O(n) operation in the worst case.
Space Complexity: O(n), due to the additional array used to represent friends.
1import java.util.LinkedList;
2import java.util.List;
3
4public class CircularGame {
5 public static int findTheWinner(int n, int k) {
6 List<Integer> friends = new LinkedList<>();
7 for (int i = 1; i <= n; i++) friends.add(i);
8 int index = 0;
9 while (friends.size() > 1) {
10 index = (index + k - 1) % friends.size();
11 friends.remove(index);
12 }
13 return friends.get(0);
14 }
15
16 public static void main(String[] args) {
17 System.out.println("Winner: " + findTheWinner(5, 2));
18 System.out.println("Winner: " + findTheWinner(6, 5));
19 }
20}In the Java solution, we utilize a `LinkedList` to store the circle of friends. We calculate the index of the friend to be eliminated and remove the friend using the `remove` method of the `LinkedList`.
The problem can be reduced to a well-known mathematical problem called the Josephus Problem. Instead of simulating each elimination, we derive the position of the winner directly using a mathematical formula.
The formula for the winner's position in the Josephus problem (0-indexed) is given by:
f(n) = (f(n-1) + k) % n for n > 1, and f(1) = 0 as the base case.
To get the result in 1-indexing that our problem requires, we add 1 to the result.
Time Complexity: O(n), iterating once for each friend.
Space Complexity: O(1), using a constant amount of space.
1using System;
2
3class CircularGame {
4 public static int FindTheWinner(int n, int k) {
5 int winner = 0;
6 for (int i = 2; i <= n; i++) {
7 winner = (winner + k) % i;
8 }
9 return winner + 1;
10 }
11
12 static void Main() {
13 Console.WriteLine("Winner: " + FindTheWinner(5, 2));
14 Console.WriteLine("Winner: " + FindTheWinner(6, 5));
15 }
16}This C# implementation efficiently determines the winner by adopting the mathematical approach of the Josephus Problem.