PROBLEM LINK:Author: Suraj Prakash DIFFICULTY:Easy PREREQUISITES:Adhoc, Implementation PROBLEMGiven a number n, find the person who survives when alternate person are killed standing in line. Explanation:IDEA 1:The idea to solve the question using the Joseph game. Firstly all the odd numbers are killed and we are left with the problem of about half the size of the original size. Now, we can solve each smaller problem and get answer based on the answer of the smaller problem. In the question, if there are n persons, then $c[n]$ denotes the survivor if we start the game from the first person, $d[n]$ denotes the survivor if there are n persons and we start the game from the second person. IDEA 2:The given problem can be formulated using the given recurrence $ans(1) = 1 $ OPTIMAL COMPLEXITY:$\mathcal{O}(N) + \mathcal{O}(Q)$ AUTHOR'S SOLUTION:Author's solution can be found here.
This question is marked "community wiki".
asked 30 Mar '16, 00:12
