Find the Winner of the Circular Game

LeetCode Problem Link

---

Theory: Josephus formula

---

Problem Context

In the Josephus problem:
1. (n) is the number of people in the circle.
2. (k) is the step size (how many people are skipped before someone is removed).
3. (J(n, k)) represents the position of the winner (last remaining person) in a circle of size (n), counting from 1.

---

Formula Explanation

The formula relates the winner's position in a circle of (n) people to the winner's position in a smaller circle of (n-1) people. Here's the step-by-step breakdown:

Step 1: Start with (J(n-1, k))

• (J(n-1, k)) gives the position of the winner in a circle with (n-1) people.
• This position is calculated relative to the smaller circle size.

Step 2: Add (k-1)

• After removing a person, we move (k-1) steps forward to simulate skipping (k) people (the (k)-th person is removed).
• The +(k-1) term adjusts the position to account for this "skipping."

Step 3: Take Modulo (n)

• When adding (k-1), the resulting position might exceed the total number of people (n). To wrap the position back into the valid range ([1, n]), we use modulo (n):

Step 4: Convert to 1-Based Index by adding 1

• Modulo arithmetic in programming is a 0-based index (i.e., starting at 0). Since the problem counts positions starting from 1, we add 1 to conver to 1-based indexing.

---

Proof of Theory

💡 Each iteration is effectively adding one person back into the "circle" and recalculating the position of the survivor as if the circle were growing.💡

---

Illustrative Example via Code solution

If the below solution is not intuitively comprehensive, try plugging in simple numbers for n and k, perhaps n=4, k=2.

Name	0-Based Index (i)	1-Based Index (i+1)
Stella	0	1
Amy	1	2
Baily	2	3
Bob	3	4

class Solution {
    public int findTheWinner(int n, int k) {
       int i=0;
       for(int j=2;j<=n;j++){
            i = (i+k)%j;
       }
        return i+1;
    }
}

Why does j start from 2?

j represents the number of people that are still playing the game. The game can only be played if there is more than one player because the last player that remains is the winner. So, our reverse calculation for the winner also starts with 2 not 1.

---

Time Complexity

The iterative approach runs in (O(n)), as it computes (J(n, k)) by looping through all circle sizes from 2 to (n).