Blog # 66 : Recruitment for Titanic

The captain of the ship 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. Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Courtesy: Vibhaj Remarks: No remarks this time. Hit again for hints. Hints: Generalize the pattern. Hit again for solution. Solution: The answer is the greatest power of 2 just less than N The problem was adapted from Codechef : http://www.codechef.com/problems/DCE05. The main problem is in optimizing the input/output. Interested students may try it out. Complexity 1. Time: O(1) 2. Space: O(1) Code: void power_2_floor(int N, int *result){ do { *result = N } while(N = (N & N-1)); }