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.
1#include <stdio.h>
2
3int findTheWinner(int n, int k) {
4 int winner = 0; // Josephus problem base case for 1 person
5 for (int i = 2; i <= n; ++i) {
6 winner = (winner + k) % i;
7 }
8 return winner + 1;
9}
10
11int main() {
12 printf("Winner: %d\n", findTheWinner(5, 2));
13 printf("Winner: %d\n", findTheWinner(6, 5));
14 return 0;
15}This C implementation uses the iterative formula for the Josephus Problem to find the winner efficiently without simulating each elimination.