Still practicing for Facebook Hacker Cup 2013:

———-
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.

Input

First line contains the number of test cases t (t<=10^5). The next t lines contain integer n, the number of applicants for that case. (n<=10^9) Output

Display t lines, each containg a single integer, the place where you would stand to win a place at TITANIC.
Example

Input:
2
5
12

Output:
4
8
———-

My Solution

The problem is not clear as to how many people will be selected at each round, so I just tried to pick the last position to be standing. By playing around with the numbers a bit I realized that there’s a clear pattern to the last position: it starts with position 2, then goes to 4, 8, 16 and so on. And more, it stays on position 2 two times, on position 4 four times, on position 8 eight times, and so on. So I used the following algorithm to solve it:

#include <stdio.h>

unsigned long long process (unsigned long long x){
  unsigned long long i;
  int counter = 0;
  int limit = 2;

  if(x==1)
    return 1;

  for (i=2;i<=x;i++){
    if(counter==limit){
      counter = 0;
      limit*=2;
    }
    counter++;    
  }  
  return limit;
}

int main(){
  int i,j;
  scanf("%d",&j);
  unsigned long long x;

  for (i=0;i<j;i++){
    scanf("%llu",&x);    
    printf("%llun",process(x));  
  }  

return 0;
}

Unfortunately it was too slow to solve all test cases within the time limit. After investigating some more I realized that we are basically going up in powers of 2, so for any number all you have to do is to find the nearest power of 2 below it, and that is your solution.

#include <stdio.h>

unsigned long long process (unsigned long long x){
  unsigned long long i;
  
  if(x==1)
    return 1;
  if(x==3)
    return 2;
  
  i = 2;

  while(i<=x)
    i*=2;

  return i/2;
}

int main(){
  int i,j;
  scanf("%d",&j);
  unsigned long long x;

  for (i=0;i<j;i++){
    scanf("%llu",&x);    
    printf("%llun",process(x));  
  }  

return 0;
}