224. The Josephus Recurrence
Challenge1000 ms256 MBSolved by 0%
n people stand in a circle, numbered 1 to n. Counting starts at person
1, and every kth person is removed. Counting then continues from the next
person, around and around, until one is left.
Print the number of the survivor.
Simulating the circle works and costs n removals from a list, which at a
million people is far too slow if each removal shifts everything after it.
The recursive insight is much better. After the first removal you have the same
problem with n-1 people, and the only difference is where the numbering
starts.
Constraints - `1 ≤ n ≤ 1000000` - `1 ≤ k ≤ 1000000`
Input
A single line containing two integers n and k.
Output
Print one integer, the position of the survivor, numbered from 1.
Input5 2
Output3
Noteis small enough to work through on paper
Input1 1
Output1
Noteis one person, who survives by default
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.