WTK  Why this kolaveri di
WHY THIS KOLAVERI DI?
Problem description:
The percentage of Soup boys in India is increasing day by day. These soup boys finally got fed up with girls cheating on them. N girls are randomly chosen and they are now under investigation. Somehow the soup boys found out that, if there are N girls, then the ratio of the number of girls who cheat to the total number of girls is (N1)/N. As these soup boys are very angry, they wanted to punish all the cheaters. But, obviously, during investigation all the girls claimed to be only one that is good. Soup boys had a plan to find the real good girl. They asked all the girls to form a circle. Then their eyes are tied. Now the leader of the soup boys goes into the middle of circle, removes the first girl from the group and then turns one step clockwise. Then leaves one girl and removes the second one. Then he leaves two girls and removes the third one and so on. The girl who is left at the end is declared as a good one and is free to go. The rest will await their surprise punishment. Being in the position of a good intelligent girl, you initially want to stand in the position which will get you free. Find such a position.
Input Specification:
The first line contains an integer T denoting the number of test cases. Then T lines follow, each with one integer N, the number of girls soup boys will choose from.
Output Specification:
For each test case output the position the good girl has to stand initially so that will be free at the end.
Input Constraints:
t<=250
n<=100000
Sample Input:
3 2 1 5Sample Output:
2 1 4Explanation of third test case:
There are 5 girls arranged in a circle as 1, 2, 3 4, 5. Girl 1 stands right next to 5. Girl 1 is removed first. Then 2 is skipped and 3 removed. The remaining girls will stand in the order 4,5,2. 4 and 5 are skipped and 2 removed. Only 4 and 5 are left and we have to skip three girls this time. We skip 454 and finally 5 is removed. So the intelligent, good girl should stand initially at 4th position.
hide comments
cegprakash:
20190502 09:32:42
@rishabh_hurr: It's in the next page of the comments ;) 

rishabh_hurr:
20190329 08:45:04
@Fata Nugraha can u again send the url of video


mynk322:
20190319 15:12:30
@Fata: Thanks for the help!! The video is very helpful.... ;) 

deathgun:
20180813 15:13:12
my 300th! :D 

mastik5h_1998:
20170919 00:29:48
good problem :)


rohit9934:
20170312 17:47:16
Thanks @Fata Nugraha.That video really helped me understanding the problem.BTW adhoc is working fine with o(n) time. Josephus problem using recursion may work but it gives me WA. 

MOHD SALMAN:
20160207 11:13:22
@Fata i think that is only for u, :P


minhthai:
20160131 17:35:17
java users, u have to implement O(n) using loop to pass 

anuveshkothari:
20150809 21:16:30
learned about josephus problem.. 

Shubham Shukla:
20150713 08:46:54
Learn't something new. Josephus you thing of beauty :* 
Added by:  cegprakash 
Date:  20111225 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 