 2

Find MSB In O(1)

Difficulty: EASY
Avg. time to solve
10 min
Success Rate
90%

Problem Statement

You are given a positive integer 'N'. Your task is to find the greatest integer less than or equal to 'N' which is a power of 2.

For Example:
If N = 14, then the nearest integer that is less than or equal to 14 and is a power of two is 8(2^3). So, the answer is 8.
Can you solve this in constant time and space complexity?
Input format:
The first line contains an integer 'T' which denotes the number of test cases. Then, the 'T' test cases area as follow.

The first and only line of each test case contains a single integer 'N'.
Output format:
For each test case, print the nearest integer that is less than or equal to 'N' and also is a power of 2.

Output for each test case will be printed in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 2 * 10^3
1 <= N <= 10^9

Time Limit: 1 second
2
4
22
4
16
Explanation for sample 1:
For the first test case, 4 itself is a power of two.
For the second test case, the nearest integer that is less than or equal to 22 and also is a power of two is 16.
2
1
63
1
32
Explanation for sample 1:
For the first test case, 1 itself is a power of two.
For the second test case, the nearest integer that is less than or equal to 63 and also is a power of two is 32.   Console