Problem

Submissions

Hints & solutions

Discuss

Find MSB In O(1)

Easy

0/40

Average time to solve is 10m

Contributed by

37 upvotes

Asked in company

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.

Follow Up:

Can you solve this in constant time and space complexity?

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
4
22

Sample Output 1:

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.

Sample Input 2:

2
1
63

Sample Output 2:

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.

Hint 1

Hint 2

Hint 3

Can you think of a brute force solution to divide N by 2 until it becomes 1?

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force

The Algorithm is as follows:

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

Time Complexity

O(log N), where N is the given number.

Space Complexity

O(1), as constant extra memory is used.

(100% EXP penalty)

Find MSB In O(1)

Console