##
**
Problem
**

Given an integer,
*
N
*
. Find a maximum integer smaller than or equal to
*
N
*
that is the power of 2.

####
**
Sample Input
**

10

####
**
Sample Output
**

8

####
**
Explanation
**

2^{3}= 8

##
**
Approach
**

We first find the position (let’s say
*
k
*
) of the most significant set bit and then compute the value of the number with a set bit at
*
k
*
-th position. This will give us the required number. This works as every number that is a power of 2 is represented as 1, 10, 100.. and so on.

###
**
Complexity Analysis
**

The time complexity is O(log(N)) with no extra space required.

####
**
C++ Programming
**

#include <bits/stdc++.h> using namespace std; int solve(int n) {// find the position of the most significant set bitint k = (int)(log2(n));// left shift 1 by kreturn 1 << k; } int main() { int n = 10; cout << solve(n); return 0; }

####
**
Output
**

8

####
**
Java Programming
**

class Solution { static int solve(int n) {// find the position of the most significant set bitint k = (int)(Math.log(n) / Math.log(2));// left shift 1 by kreturn 1 << k; } public static void main(String arg[]) { int n = 10; System.out.print(solve(n)); } }

####
**
Output
**

8

####
**
Python Programming
**

import math def solve(n): # find the position of the most significant set bit k = int(math.log(n, 2)) # left shift 1 by k return 1 << k n = 10 print(solve(n))

####
**
Output
**

8

**
People are also reading:
**

- Find MSB in O(1)
- Longest Substring without repeating characters
- Count subarrays with given XOR
- Python Take list as an input from a user
- Delete Nodes And Return Forest
- Longest Consecutive Sequence in Linear time
- Modular Exponentiation in Logarithmic Time
- Rearrange an array such that arr[i] = i
- Minimum Edit Distance
- The Stock Span Problem

## Leave a Comment on this Post