231. Power of Two

EasyBit ManipulationRecursionMath

Problem Description

The problem provides us with a single integer n and asks us to determine if this number is a power of two. To rephrase, the question is asking if there exists another integer x such that 2 raised to the power x equals n (mathematically, this can be represented as n == 2^x). We need to return true if n is indeed a power of two, and false otherwise.

Intuition

To determine whether a given number is a power of two, we can use a simple observation about binary representations of powers of two. A power of two in binary is represented as a 1 followed by zeros. For example, 2^2 is 4 in decimal and 100 in binary, and 2^3 is 8 in decimal and 1000 in binary.

We know that subtracting 1 from a power of two will result in a binary number where the set bit (1) of the power of two turns to 0, and all following bits turn to 1. For example, if n is 4 (100 in binary), then n - 1 is 3 (011 in binary). Using bitwise AND operation (&) between n and n - 1, every corresponding pair of bits are compared; the result is 1 only if both bits are 1. Since n - 1 has 1s where n has 0s, their AND result will always be 0 if n is a power of two.

The condition n > 0 ensures that we exclude non-positive numbers, as only positive integers can be powers of two. Combining these two conditions with the logical AND operator (the and keyword in Python), which only results in true when both expressions are true, provides us with the correct check for whether n is a power of two.

In conclusion, n > 0 and (n & (n - 1)) == 0 succinctly checks whether n is a positive integer and a power of two by exploiting the characteristics of powers of two in binary representation.

Learn more about Recursion and Math patterns.

Solution Approach

The implementation of the solution is quite straightforward and does not involve complex data structures or algorithms. Instead, it uses bitwise operations, which are a fundamental part of lower-level programming languages and concepts.

Here's a step-by-step breakdown of the implementation:

Check if n is greater than 0. This step is essential because we're only interested in positive integers since negative integers and zero cannot be powers of two.
Perform a bitwise AND operation between n and n-1. Here's how it works:
- When n is a power of two, its binary representation has exactly one bit set to 1, and all other bits set to 0. Example: 4 in binary is 100.
- Subtracting 1 from n flips the least significant 1 to 0 and all the bits to the right of it to 1 (if any). Example: 3 is 011 in binary.
- A bitwise AND operation between these two numbers n & (n - 1) results in zero because there are no positions with a 1 in both numbers. This is unique to powers of two.
The result of the bitwise AND operation is compared with 0 using the equality == operator.
The logical AND operator and is finally used to return True only if both the above checks pass, which means n is greater than 0, and the result of n & (n - 1) is equal to 0, verifying that n is indeed a power of two.

To summarize, the one-liner n > 0 and (n & (n - 1)) == 0 elegantly combines the necessary checks using bitwise and logical operators to determine if an integer is a power of two. It's efficient since these operations are performed at the bit level and usually take constant time.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach using the example of n = 8.

First, we check if n is greater than 0. For n = 8, this is true since 8 is a positive number.
Next, we perform a bitwise AND operation between n and n-1. In binary:
- n is 8 which is 1000 in binary.
- n-1 is 7 which is 0111 in binary.
- Performing a bitwise AND operation: 1000 & 0111 gives 0000.
The result of this bitwise AND operation is 0.
Finally, we combine the checks: n > 0 and (n & (n - 1)) == 0. In this case, both are true.

So, for n = 8, the conditions hold true. The result of 8 > 0 and (8 & (7)) == 0 is true, which means that the number 8 is indeed a power of two. This method works efficiently for any positive integer and is especially quick to compute using bitwise operations.

Solution Implementation

1class Solution:
2    def is_power_of_two(self, n: int) -> bool:
3        # Check if the number is greater than 0 and only one bit is set.
4        # The expression (n & (n - 1)) will be 0 only for powers of two,
5        # because there is only one bit set in a power of two, and (n - 1)
6        # will have all the bits set before that single bit in n.
7        return n > 0 and (n & (n - 1)) == 0
8
9# The method is_power_of_two can be used as:
10# result = Solution().is_power_of_two(16)
11# print(result)  # Output: True, because 16 is a power of two
12

1class Solution {
2    /**
3     * Checks if a number is a power of two.
4     *
5     * A power of two has exactly one bit set in binary representation.
6     * If we subtract 1 from a number which is a power of 2 (e.g., 8 is 1000 in binary),
7     * we get a number which has all the bits set after the bit that was set in original number (e.g., 7 is 0111).
8     * Taking an AND of n and n-1 will yield 0 if n is a power of two.
9     *
10     * @param n The number to be checked.
11     * @return true if n is a power of two, false otherwise.
12     */
13    public boolean isPowerOfTwo(int n) {
14        // Check if n is greater than 0 and if n AND (n-1) is 0
15        return n > 0 && (n & (n - 1)) == 0;
16    }
17}
18

1class Solution {
2public:
3    // Function to check if a number is a power of two
4    bool isPowerOfTwo(int number) {
5        // A power of two has only one bit set in binary representation.
6        // Subtracting one from such a number flips all the bits after
7        // the set bit (including the set bit). Performing an AND operation
8        // between the number and number - 1 would then result in zero.
9        // Additionally, the number must be positive to be a power of two.
10        return number > 0 && (number & (number - 1)) == 0;
11    }
12};
13

1// This function checks if a given number is a power of two.
2// It uses bitwise AND to determine if there is only one bit set in the binary representation.
3// The number should be greater than zero since 0 is not a power of two.
4// Parameters:
5// n - The number to check if it is a power of two.
6// Returns:
7// A boolean indicating whether the number is a power of two (true) or not (false).
8function isPowerOfTwo(n: number): boolean {
9    // Check if 'n' is greater than 0 to avoid non-positive integers.
10    // (n & (n - 1)) will be 0 for powers of two since these numbers have a single high bit.
11    // For example, 4 in binary is 100, and 3 is 011. Bitwise AND is 000.
12    return n > 0 && (n & (n - 1)) === 0;
13}
14

Time and Space Complexity

The time complexity of the code is O(1) because the operation performed is a bitwise AND operation and a comparison, both of which take constant time regardless of the size of the integer n.

The space complexity of the code is also O(1) as it does not use any additional memory that grows with the input size. The function only uses a fixed amount of space to store the input and output variables.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1

dp[i] = dp[i] + dp[i - 1]

dp[i] = (dp[i] + dp[j] + 1) for j in 0 to i

dp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don’t know