Sponsored
Sponsored
This approach involves continuously dividing the number n by 2. During each iteration, if n is divisible by 2, we continue the process. However, if n becomes 1 exactly, it's clear that the original n was a power of two. If n ever becomes an odd number greater than 1 during the division process, it means n is not a power of two.
The time complexity is O(log(n)) as we are dividing n by 2 each time. The space complexity is O(1) because no additional space is used.
1public class PowerOfTwo {
2 public boolean isPowerOfTwo(int n) {
3 if (n < 1) return false;
4 while (n % 2 == 0) n /= 2;
5 return n == 1;
6 }
7}The Java solution is identical in logic to the C and C++ versions, dividing n by 2 until it checks if n is 1.
This approach uses the property that if n is a power of two, then n & (n - 1) should be 0. This is because a power of two in binary form means there is only one '1' bit. Subtracting 1 from it flips all the bits after the last '1'. If the bitwise AND results in 0, n is a power of two.
The time complexity is O(1) because it's a constant-time operation, and the space complexity is also O(1).
1In Python, this solution uses bitwise operations to efficiently check if n is a power of two.