Find MSB In O(1)

Posted: 26 Jan, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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.
Follow Up:
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
Approach 1

The Algorithm is as follows:

 

  1. Create an ‘ANS’ variable and initialize it to 1.
  2. While ‘N’ != 1, do:
    1. ‘N’ = ‘N’ / 2.
    2. ‘ANS’ = ‘ANS’ * 2.
  3. Finally, return ‘ANS’.
Try Problem