Josephus Problem
Problem Description
n people stand in a circle (0-indexed: 0 to n-1). Starting from person 0, count k people clockwise and eliminate the k-th person. Repeat from the next person. Return the 0-indexed position of the last survivor.
Example 1:
Input: n=5, k=2
Output: 2
Example 2:
Input: n=6, k=2
Output: 4
Example 3:
Input: n=7, k=3
Output: 3
DE Shaw Tier 2 — classic problem.
O(n) recurrence: josephus(1,k)=0; josephus(n,k)=(josephus(n-1,k)+k)%n
Naive simulation: O(n^2). For expected O(n*sqrt(n)) see sqrt-decomposition variant.
Talk-track: 'The recurrence shifts the position by k each round, modulo the shrinking circle size.'
Example Test Cases
Example 1
Input: [5,2]
Expected: 2
Example 2
Input: [6,2]
Expected: 4
Example 3
Input: [7,3]
Expected: 3
Example 4
Input: [1,2]
Expected: 0
Run your code to see the results