Description
In a circular game with n friends, every kth person is eliminated until one remains. Return the winner (Josephus problem).
Examples
Input:
n = 5, k = 2Output:
3Explanation:
Person 3 wins.
Input:
n = 3, k = 1Output:
3Explanation:
With k=1, eliminating every 1st person (the current person). Starting with persons 1, 2, 3: eliminate 1 (leaving 2,3), eliminate 2 (leaving 3), so person 3 wins. This shows the edge case where k=1.
Input:
n = 4, k = 3Output:
1Explanation:
Starting with persons 1, 2, 3, 4, eliminating every 3rd person: eliminate 3 (leaving 1,2,4), then counting from 4: eliminate 2 (leaving 1,4), then counting from 4: eliminate 4 (leaving 1). Person 1 wins.
Constraints
- •
1 ≤ k ≤ n ≤ 500