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.
1def is_power_of_two(n: int) -> bool:
2 if n < 1:
3 return False
4 while n % 2 == 0:
5 n //= 2
6 return n == 1This Python function performs an iterative division similar to the C/C++/Java solutions, refined with Python syntax.
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).
1Leveraging Java's bit manipulation capabilities, this solution offers a clean and efficient way to check for a power of two using bit operations.