Josephus Algorithm

Problem Link

Click Here

Approaches

Approach 1 (Brute force)

1. we will create one array/vector to store the values from 1 to n, representing the sequence of each person

2. As given in the question we will remove one person from the array and move forward with the next iterations

3. But the problem here is how will you reach the 0th index after 5? by using this formula given (index+1)%n

4. At last when the size of the array, which in this case is nums.size() == 1, we will stop and return the value.

Complexity

Time Complexity O(n)

Space complexity O(n)

Approach 2 (Optimal)

use Josephus algorithm

read about Josephus Problem here, for video explanation click here

This is a recursion-based problem but we can use this in the loop.

1. Since the Josephus algorithm is for the zero-based indexing problem based on circles, we later need to optimize our answer according to the 1-based indexing

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

All the best for your DSA journey! Let me know your feedback so that we can improve this article together.

Ujjwal Sharma