Power of Two
LeetCode Problem #231 (Easy)
Problem Statement
Given an integer, write a function to determine if it is a power of two.
Testcases
Example 1:
Input: 1
Output: true
Explanation: 2^0 = 1
Example 2:
Input: 16
Output: true
Explanation: 2^4 = 16
Example 3:
Input: 218
Output: false
Problem Explanation
A number is a power of two if it can be formed by repeatedly multiplying some number of 2's.
16 is a power of 2 since 16 = 2 * 2 * 2 * 2.
This can alternatively be written as 16 = 2^4.
We must determine whether a particular number is a power of two.
Example:
If n = 16
16 / 2 = 8
8 / 2 = 4
4 / 2 = 2
2 / 2 = 1 and 2 % 2 = 0 -> return true
If n = 17
17 / 2 = 8
17 % 2 = 1 and n != 1 -> return false
Algorithm
Iterative Approach
If the number is 0, it cannot be a power of 2.
If the number is 1, since 2 ^ 0 = 1, it is a power of 2.
Iteratively reduce the power of the number by dividing by 2.
a. If the number % 2 yields a remainder and is not 1, then it is not a power of 2.
b. If the number evenly divides 2 and yields no remainder, it is a power of 2.
Code
bool isPowerOfTwo(int n) {
// If the number is 0, it cannot be a power of 2
if(n == 0) {
return false;
}
// If a number does not divide 2 evenly and is not 1 (since, 2 / 2 = 1), then return false
while(n != 1) {
if(n % 2 != 0) {
return false;
}
// Iteratively divide the number by 2 to reduce the power
n /= 2;
}
return true;
}
Last updated
Was this helpful?