Power Of Two - Leetcode Solution

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:

1. If n == 0, return False.
2. While n % 2 == 0, divide n by 2.
3. 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:

1. If n == 0, return False.
2. 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.

1