Relation to find the last standing person in a circle. Possible variant of Josephus problem

135 Views Asked by At

Consider a set of N people standing in a circle, we kill the first person, spare the second, kill the third person and so on.. Find the last standing person in the circle.

I think this might be the same as the Josephus problem but I'm not entirely sure and would appreciate any insight on approaching the problem.

1

There are 1 best solutions below

2
On BEST ANSWER

Yes, it is the $k=2$ case of the Josephus problem, but you are off by one from the classic formulation because you kill the first instead of the second. Take the classic solution, then subtract one from the last one standing to account for that. If the classic last standing is $1$, it will be $N$ as the subtraction should be done $\bmod N$