Problem : SHUFFL Have you ever tried to solve Joshephus Problem. The problem is here : josephus. In joshephus problem we are basically removing 1 people each time by some rules indicated in the problem statement. Similarly for our problem we are removing 2 people each time again by rules depicted in the problem statement. There is a nice recursive solution for josephus problem which is here or you can look recursive equation in wiki page itself. Basically in josephus problem f(n) is written in terms of f(n1). While in our problem we have write f(n) in terms of f(n2). You can see the function getIndices() for knowing recursive equation : https://www.codechef.com/viewsolution/16372240 Detailed Explanation Brute force :
So however this brute force will take O (N^2). Lets optimize it. Why pass the array all time to the function. Because our approach is independent of values of the array, it just depends on indices so instead just pass n and recreate the remaning elements using the map.
So now you are saved from passing the new array each time to the recursive function. But it is still O (N^2) because you are still creating new array. So what you should do is without creating the new array get the corresponding 2 remaning indices on the fly.
And here is the getMappedIndex function
So now clearly it is O (N) as getMappedIndex works in O (1). If you have any doubt in understanding, please comment. asked 25 Nov '17, 23:33

i think there is a typo. josephus problem f(n) is written in terms of f(n1) not f(n2).
Thanks @jjtomar for pointing the typo
no worries mate @aayushkapadia