How this soln https://www.codechef.com/viewsolution/16351075 comes can anyone explain in detail
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 
1 Like