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.
1function findTheWinner(n, k) {
2 let friends = Array.from({ length: n }, (_, i) => i + 1);
3 let index = 0;
4 while (friends.length > 1) {
5 index = (index + k - 1) % friends.length;
6 friends.splice(index, 1);
7 }
8 return friends[0];
9}
10
11console.log("Winner:", findTheWinner(5, 2));
12console.log("Winner:", findTheWinner(6, 5));In JavaScript, an array is used to manage friends, with `splice` employed to remove the k-th friend, iterating until the winner is determined.
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.
1public class CircularGame {
2 public static int findTheWinner(int n, int k) {
3 int winner = 0;
4 for (int i = 2; i <= n; i++) {
5 winner = (winner + k) % i;
6 }
7 return winner + 1;
8 }
9
10 public static void main(String[] args) {
11 System.out.println("Winner: " + findTheWinner(5, 2));
12 System.out.println("Winner: " + findTheWinner(6, 5));
13 }
14}The Java solution efficiently applies the Josephus iterative approach, calculating the winner in linear time.