grid47 Exploring patterns and algorithms
Oct 14, 2024
4 min read
Solution to LeetCode 231: Power of Two Problem
Given an integer n, determine if it is a power of two. An integer n is considered a power of two if there exists an integer x such that n == 2^x.
Problem
Approach
Steps
Complexity
Input: The input consists of a single integer n (−2^31 <= n <= 2^31 − 1).
Example: Input: n = 8
Constraints:
• -2^31 <= n <= 2^31 - 1
Output: Return true if n is a power of two, otherwise return false.
Example: Output: true
Constraints:
Goal: The goal is to verify whether the number n is a power of two using bit manipulation.
Steps:
• Check if n is less than or equal to zero, in which case it is not a power of two.
• Perform a bitwise AND operation between n and (n - 1). If the result is zero, then n is a power of two.
Goal: The input integer n must lie within the range of a 32-bit signed integer.
Steps:
Assumptions:
• The input will be a valid integer within the specified range.
• n may be negative or zero, but only positive values can be a power of two.
• Input: Input: n = 8
• Explanation: Since 8 can be written as 2^3, it is a power of two. Thus, the output is true.
• Input: Input: n = 5
• Explanation: 5 cannot be written as 2^x for any integer x, so the output is false.
Approach: We can solve this problem using bit manipulation to determine if n is a power of two.
Observations:
• A number n is a power of two if it has exactly one bit set in its binary representation.
• Using the bitwise AND operation (n & (n - 1)), we can quickly check if a number is a power of two. This operation will return zero only for numbers that are powers of two.
Steps:
• Check if n is greater than zero.
• Perform the operation n & (n - 1). If the result is 0, then n is a power of two.
• Return true if the result is zero, otherwise return false.
Empty Inputs:
• No empty inputs are possible since the input is an integer.
Large Inputs:
• For large values of n, ensure the solution works within the given integer range.
Special Values:
• If n is 0 or negative, it cannot be a power of two.
Constraints:
• Ensure that the solution works efficiently within the given constraints.
Defines the function `isPowerOfTwo` that takes an integer `n` as input and returns a boolean value indicating whether `n` is a power of two.
2 : Condition Check
if(n <=0) returnfalse;
Checks if `n` is less than or equal to 0, in which case it cannot be a power of two. If true, returns `false`.
3 : Bitwise Operation
return!(n & (n -1));
Uses a bitwise AND operation between `n` and `n-1` to check if only one bit is set in `n`. If true, the number is a power of two, and it returns `true`; otherwise, it returns `false`.
Best Case: O(1)
Average Case: O(1)
Worst Case: O(1)
Description: The time complexity is constant, O(1), because we are performing only one bitwise operation to check if the number is a power of two.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is constant, O(1), because we are using only a few variables and no additional data structures.
