This question is from code chef, named Odd. I believe this
is a good problem to play with for all levels. If I can solve it surely
anyone else can, cough * only if pi is fake* cough*.
Here is the question :
The captain of the ship TITANIC is a little .... off the track. He needs to select the crew for the ship. But everyone seems to be eligible. So to test their intelligence, he plays a game. The contestants have to stand in a line. They are given the numbers in the order in which they stand, starting from 1. The captain then removes all the contestants that are standing at an odd position. Initially, standing people have numbers - 1,2,3,4,5... After first pass, people left are - 2,4,... After second pass - 4,.... And so on. You want to board the ship as a crew member. Given the total number of applicants for a position, find the best place to stand in the line so that you are selected. [B]Input[/B] First line contains the number of test cases t (t<=10^6). The next t lines contain integer n, the number of applicants for that case. (n<=10^9) [B]Output[/B] Display t lines, each containg a single integer, the place where you would stand to win a place at TITANIC. Example (Added) *Comments below not needed in the output; Input: 2 //number of inputs 5 //number of applicants 12 //number of applicants Output: 4 //best position 8 //best position
Here are the specifications :
Time limit: 1s Source limit: 50000 Language any for here.
I was analyzing it and found a pattern and solved the question.
Remember brute force wont work because of the TIME LIMIT for
one's application, although it might be helpful to get a program
Hope to see some solutions. Here is the page to the problem as well. Kudos, if someone does it faster than my time, 0.70 seconds.
If the instruction is not clear then ask.
Remember : Follow regular coding rules( neat, clean, readable ... ).