Python 0231.py
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
if n == 0:
return False
return (n & (n-1)) == 0
Difficulty
and has an acceptance rate of about 50% (4+ million submissions).
Typical patterns to solve this problem:
- Bit Manipulation
- Math
- Recursion
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation determines whether a given integer n is a power of two. It follows a classic bit-manipulation technique that runs in constant time and uses only a few elementary operations. The logic is encapsulated in a single method of a Solution class, making it straightforward to integrate into larger codebases or testing frameworks.
Core Logic
The method consists of two distinct steps. The first step eliminates the special case where n equals zero, because zero is not a power of two. The second step applies a bitwise test that exploits the binary representation of powers of two.
if n == 0:
return False
If the input passes this guard, the method evaluates the expression n & (n-1). For any positive integer that is a power of two, its binary form contains exactly one set bit (e.g., 8 is 1000). Subtracting one flips that solitary set bit to zero and turns all lower bits to one (e.g., 7 is 0111). Performing a bitwise AND between the original number and its predecessor therefore yields zero only for powers of two.
return (n & (n-1)) == 0
The combination of the guard and the bitwise comparison yields the final Boolean result.
Edge Cases Handled
The implementation explicitly checks for n == 0, ensuring that the method returns False for this input. This is necessary because the bitwise expression would otherwise evaluate to True for zero (0 & -1 == 0).
Negative integers are also processed correctly. In two’s-complement representation, negative numbers have more than one set bit, so the expression n & (n-1) does not produce zero. Consequently, the method returns False for all negative inputs without requiring an additional conditional check.
Performance Optimizations
The algorithm runs in constant time because it performs a fixed number of primitive operations: one equality comparison, one subtraction, one bitwise AND, and one equality check. No loops, recursion, or division operations are involved, which eliminates overhead associated with iterative or arithmetic approaches.
By returning early for the zero case, the method avoids the unnecessary computation of the bitwise expression when the outcome is already known. This early exit contributes to a marginal reduction in instruction count, especially in scenarios where zero is a frequent input.
The use of a single bitwise operation (&) leverages hardware-level instructions that are typically executed in a single CPU cycle, making the solution highly efficient on modern processors.
Overall, the code achieves the desired functionality with minimal computational effort and memory usage.
ELI5 - Simplified Explanation
Imagine a special box that holds numbers. This code is like a little checker that looks at a number to see if it belongs to a magic family called the powers of two. The powers of two are numbers like two, four, eight, and sixteen, which grow by doubling over and over.
First, the code peeks at the number. If the number is zero, it knows right away that zero cannot be in this special family.
Then, there is a very clever trick using binary bits. Computers see numbers as stacks of little light bulbs that are either off or on. When a number is a power of two, it has exactly one light bulb turned on. By taking the number and a version of itself minus one, the code performs a secret handshake. If the result of that handshake is zero, it means the number has that perfect single light bulb, so it is a power of two. If the result is anything else, the number belongs to a different family.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | ||||||||||
| www | AlgoMonster | C++ | Python | Java | TS | ||||||
| WalkCCC | C++ | Python | Java | ||||||||
| leetcode.ca | C++ | Python | Java | Rust | JS | Go | TS | ||||
| LeetcodeHelp | C++ | Python | Java | ||||||||
| MemoryLimitExceeded | C++ | Python | |||||||||
| Progiez | C++ | Python | Java | ||||||||
| github | aylei | Rust | |||||||||
| BigEggStudy | C# | ||||||||||
| black-shadows | C++ | ||||||||||
| charles-wangkai | Java | ||||||||||
| chenyanzhe | C++ | ||||||||||
| DimitrisJim | C | ||||||||||
| everthis | JS | ||||||||||
| fartem | Ruby | ||||||||||
| fengvyi | C++ | ||||||||||
| fpdjsns | C++ | ||||||||||
| gaosq0604 | Python | ||||||||||
| halfrost | Go | ||||||||||
| haoel | C++ | ||||||||||
| JoshCrozier | JS | ||||||||||
| keineahnung2345 | C++ | ||||||||||
| Krazune | C++ | ||||||||||
| lennylxx | C | ||||||||||
| linouk23 | C++ | ||||||||||
| lkwq007 | Python | ||||||||||
| muhammadfarhankt | Go | ||||||||||
| pruthvikp | Python | ||||||||||
| qiyuangong | Python | ||||||||||
| ruoru | Rust | ||||||||||
| shreymehul | C# | ||||||||||
| suxrobGM | C# | ||||||||||
| trung-hn | Python | ||||||||||
| varunu28 | Java | ||||||||||
| vli02 | C | ||||||||||
| vthwang | Java | ||||||||||
| zfang399 | C++ | ||||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||||
| WalkCCC | C++, Python, Java | ||||||||||
| leetcode.ca | C++, Go, Java, JavaScript, Python, Rust, TypeScript | ||||||||||
| LeetcodeHelp | C++, Java, Python | ||||||||||
| MemoryLimitExceeded | Python, C++ | ||||||||||
| Progiez | C++, Java, Python | ||||||||||
| aylei | Rust | ||||||||||
| BigEggStudy | C# | ||||||||||
| black-shadows | C++, C++ | ||||||||||
| charles-wangkai | Java | ||||||||||
| chenyanzhe | C++ | ||||||||||
| DimitrisJim | C | ||||||||||
| everthis | JavaScript | ||||||||||
| fartem | Ruby | ||||||||||
| fengvyi | C++ | ||||||||||
| fpdjsns | C++ | ||||||||||
| gaosq0604 | Python | ||||||||||
| halfrost | Go | ||||||||||
| haoel | C++ | ||||||||||
| JoshCrozier | JavaScript | ||||||||||
| keineahnung2345 | C++ | ||||||||||
| Krazune | C++ | ||||||||||
| lennylxx | C | ||||||||||
| linouk23 | C++ | ||||||||||
| lkwq007 | Python | ||||||||||
| muhammadfarhankt | Go | ||||||||||
| pruthvikp | Python | ||||||||||
| qiyuangong | Python | ||||||||||
| ruoru | Rust | ||||||||||
| shreymehul | C# | ||||||||||
| suxrobGM | C# | ||||||||||
| trung-hn | Python | ||||||||||
| varunu28 | Java | ||||||||||
| vli02 | C | ||||||||||
| vthwang | Java | ||||||||||
| zfang399 | C++ |
Videos
Similar Problems
- problem 191: Number of 1 Bits
- problem 326: Power of Three
- problem 342: Power of Four
Solved On The Same Day
- problem 232: Implement Queue using Stacks
- problem 258: Add Digits
- problem 268: Missing Number
- problem 326: Power of Three
- problem 338: Counting Bits
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality