Given an integer n, return true if it is a power of two. Otherwise, return false.
An integer n is a power of two, if there exists an integer x such that n == 2x.
Example 1:
Input: n = 1
Output: true
Explanation: 20 = 1
Example 2:
Input: n = 16
Output: true
Explanation: 24 = 16
Example 3:
Input: n = 3
Output: false
Constraints:
- -231 <= n <= 231 - 1
My Solution
To solve this problem one thing to recognize is that all powers of two have only one set bit in their binary representation. We can just count the number of set bits in the number and check whether it equals 1. We also need to make sure that if a number is negative we return false right away since a negative number can never be a power of two.
Time complexity would be O(1) because checking all the bits require a maximum of 32 iterations which is constant. Space complexity is O(1) because we only require constant extra space.
class Solution {
public boolean isPowerOfTwo(int n) {
if (n < 0) {
return false;
}
int bits = 0;
while (n > 0) {
bits += (n & 1);
n >>= 1;
}
return (bits == 1);
}
}