Solution For Power Of Two
Problem statement: Given an integer n, determine if it is a power of two.
Solution:
Approach #1 Brute Force
One simple way to find out whether a number n is a power of 2 is to keep dividing it by two as long as the result is an integer so that 2^n / 2^n-1 = 2^1 = 2.
If the result is 1, then n is a power of 2, otherwise not.
Algorithm:
- If n == 0, return False.
- While n % 2 == 0, divide n by 2.
- If n == 1, return True, otherwise return False.
Time Complexity: O(log n)
Approach #2 Bitwise-AND
Another way to solve this problem is to use the bitwise-AND operator.
If n is a power of 2, it means that n is of the form 2^k, where k is a non-negative integer. In binary form, such a number has only one bit set to 1. For example,
2^3 = 8 (00001000 in binary)
2^5 = 32 (00100000 in binary)
Taking the bitwise-AND of n and n-1 removes the last set bit of n. If n is a power of 2, the result will be 0.
Algorithm:
- If n == 0, return False.
- Return n & (n-1) == 0.
Time Complexity: O(1)
Code (Python) – Approach #1 Brute Force
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
if n == 0:
return False
while n % 2 == 0:
n //= 2
return n == 1
Code (Python) – Approach #2 Bitwise-AND
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
return n != 0 and (n & (n-1)) == 0
Code (Java) – Approach #2 Bitwise-AND
class Solution {
public boolean isPowerOfTwo(int n) {
return n != 0 && (n & (n-1)) == 0;
}
}
Note: The bitwise-AND operator & has lower precedence than !=, so the brackets are necessary.
Step by Step Implementation For Power Of Two
class Solution { // function to check if given number is power of two public boolean isPowerOfTwo(int n) { // if number is 0, it is not a power of two if(n == 0) { return false; } // loop until n becomes 1 while(n != 1) { // if n is not divisible by 2, it is not a power of two if(n % 2 != 0) { return false; } // divide n by 2 n = n / 2; } // if n becomes 1, it is a power of two return true; } }
def isPowerOfTwo(n): if (n == 0): return False while (n != 1): if (n % 2 != 0): return False n = n // 2 return True
var isPowerOfTwo = function(n) { // if n is less than or equal to 0, it is not a power of two if (n <= 0) { return false; } // if n is a power of two, then it's binary representation will only have one '1' bit // we can use the built-in function to count the number of '1' bits in a number return n.toString(2).split('0').length === 1; };
bool isPowerOfTwo(int n) { if (n == 0) return false; while (n != 1) { if (n%2 != 0) return false; n = n/2; } return true; }
using System; class GFG { // Function to check whether // x is power of 2 static bool isPowerOfTwo(int x) { // Condition to check // if x is power of 2 if (x == 0) return false; return (x & (x - 1)) == 0; } // Driver Code public static void Main() { int n = 32; if(isPowerOfTwo(n)) Console.Write("Yes"); else Console.Write("No"); } }