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.
1function findTheWinner(n, k) {
2 let winner = 0;
3 for (let i = 2; i <= n; i++) {
4 winner = (winner + k) % i;
5 }
6 return winner + 1;
7}
8
9console.log("Winner:", findTheWinner(5, 2));
10console.log("Winner:", findTheWinner(6, 5));
The JavaScript solution computes the winner by applying the Josephus iterative formula cleanly within a loop.