How to solve this?

How this soln CodeChef: Practical coding for everyone comes can anyone explain in detail

question DCE05 Problem - CodeChef

let’s try to play the game for n = 5

1 2 3 4 5 -> 2 4 -> 4

for n = 7 : 1 2 3 4 5 6 7 -> 2 4 6 -> 4

for n = 8 : 1 2 3 4 5 6 7 8 -> 2 4 6 8 -> 4 8 -> 8

now, we can see that after each turn players that are removed get multiplied by 2 (first (1 3 5…) then (2 6 10…) then(4 8 12…)) and after n turns the players in first position is (2^n). So, if we assume that the game will end after k turns(i.e. after k turn only one player left) so, out answer will be 2^k !

Now, the only thing to left is to find k. as we can see that after each turn players count becomes half so, clearly the game will end after log2(N) turns.

hope it helps . if u still have doubts feel free to ask :slight_smile:

1 Like

This is the Josephus problem: Josephus problem - Wikipedia

1 Like