Odd Solution | CodeChef

Problem

The captain of the ship TITANIC needs to select the crew for the ship. 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.

CodeChef Problem Link

Input

First line of input contains an integer T, denoting the number of test cases. The next T lines contain integer n, the number of applicants for that case.

Output

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

Constraints

• 1 <= T ≤ 100000
• 1 <= n ≤ 10^9

Sample Input

2
5
12

Sample Output

4
8

Solution

Code Implementation

//
//  main.cpp
//  Odd
//
//  Created by Himanshu on 19/02/22.
//

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int T;
    long n;
    cin>>T;
    
    while (T--) {
        long two=2, i=1;
        cin>>n;
        
        while ((n/two) != 1) {
            i++;
            two = pow(2,i);
        }
        
        cout<<two<<endl;
    }

    return 0;
}

Time Complexity: O(logn)