Problem Statement:
Write a recursive function isPowerOfTwo(n) that returns true if n is a power of 2, otherwise false.
Example 1:
Input: 8
Process: (8 → 4 → 2 → 1)
Output: true
Example 2:
Input: 18
Output: false
Concepts:
- Power of Two: A number is a
power of 2if it can be divided by2repeatedly until it reaches1. - Base Case:
n == 1 → true - Invalid Case: n < 1 or n % 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
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
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)
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);
}
}
#include <iostream>
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);
}
};
#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);
}
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);
}
}
