Write a recursive function isPowerOfTwo(n) that returns true if n is a power of 2, otherwise false.
Concepts
- Power of Two: A number is a power of 2 if it can be divided by 2 repeatedly until it reaches 1.
- Base Case:
n == 1 → true - Invalid Case:
n < 1orn % 2 != 0 → false - Recursive Case:
isPowerOfTwo(n / 2)
Time & Space Complexity
- Time Complexity:
O(log n) - Space Complexity:
O(log n)(due to recursion stack)
Examples
Input: 8
Output: true (8 → 4 → 2 → 1)
Input: 18
Output: false
function isPowerOfTwo(n) {
if (n === 1) return true;
else if (n < 1 || n % 2 !== 0) return false;
return isPowerOfTwo(n / 2);
}
console.log(isPowerOfTwo(8)); // true
console.log(isPowerOfTwo(18)); // false
#include <stdbool.h>
bool isPowerOfTwo(int n) {
if (n == 1)
return true;
else if (n < 1 || n % 2 != 0)
return false;
return isPowerOfTwo(n / 2);
}
class Solution {
public:
bool isPowerOfTwo(int n) {
if (n == 1)
return true;
else if (n < 1 || n % 2 != 0)
return false;
return isPowerOfTwo(n / 2);
}
};
class Solution {
public boolean isPowerOfTwo(int n) {
if (n == 1)
return true;
else if (n < 1 || n % 2 != 0)
return false;
return isPowerOfTwo(n / 2);
}
}
class Solution(object):
def isPowerOfTwo(self, n):
"""
:type n: int
:rtype: bool
"""
if n == 1:
return True
elif n < 1 or n % 2 != 0:
return False
return self.isPowerOfTwo(n // 2)
public class Solution {
public bool IsPowerOfTwo(int n) {
if (n == 1)
return true;
else if (n < 1 || n % 2 != 0)
return false;
return IsPowerOfTwo(n / 2);
}
}
