Problem 231

Abstract / Summary

Determine if a given number can be expressed as a power of two.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 0231.py

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n == 0:
            return False

        return (n & (n-1)) == 0
6 lines | 143 bytes | submitted August 12, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 50% (4+ million submissions).

Typical patterns to solve this problem:
  • Bit Manipulation
  • Math
  • Recursion
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 9 | μ = 8.33 | σ = 1.92

Complexity Analysis

Time: constant
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
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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++
52 links | 36 authors | 10 languages

Videos

These are a few popular YouTube videos for this problem:
YouTube video 'Power of Two | Check if a number is Power of Two | Bit Manipulation Interview Questions'
Pepcoding 8 mins
Power of Two | Check if a number is Power of Two | Bit Manipulation Interview Questions
YouTube video 'Power of Two LeetCode Solution in Java | Optimized O(1) Approach  | Placement Interview Questions'
Jenny's Lectures CS IT 13 mins
Power of Two LeetCode Solution in Java | Optimized O(1) Approach | Placement Interview Questions
YouTube video 'Power of Two | Multiple Approaches | Leetcode 231 | codestorywithMIK'
codestorywithMIK 18 mins
Power of Two | Multiple Approaches | Leetcode 231 | codestorywithMIK
YouTube video 'Power of Two | LeetCode 231 | C++, Java, Python'
Knowledge Center 10 mins
Power of Two | LeetCode 231 | C++, Java, Python
YouTube video 'Power of two 🔥 | Leetcode 231 | Bit Manipulation | 4 approaches'
Ayushi Sharma 10 mins
Power of two 🔥 | Leetcode 231 | Bit Manipulation | 4 approaches
YouTube video 'Power of Two | LeetCode 231 | Check If Number is Power of 2 using Bitwise Operator'
Programming Tutorials 8 mins
Power of Two | LeetCode 231 | Check If Number is Power of 2 using Bitwise Operator
YouTube video 'Easy Meta Coding Interview Question - Power Of Two - JavaScript'
AlgoJS 6 mins
Easy Meta Coding Interview Question - Power Of Two - JavaScript
YouTube video 'Power of Two (Leetcode 231) - Easy'
The Hustling Engineer 19 mins
Power of Two (Leetcode 231) - Easy
YouTube video 'Power of Two - LeetCode 231 - Python #leetcode #binary'
Deepti Talesra 9 mins
Power of Two - LeetCode 231 - Python #leetcode #binary
YouTube video '231. Power of Two | Bit Manipulation | Remove Last Set Bit'
Aryan Mittal 12 mins
231. Power of Two | Bit Manipulation | Remove Last Set Bit
YouTube video 'LeetCode Problem: 231. Power of Two | Java Solution'
Code for Interview 6 mins
LeetCode Problem: 231. Power of Two | Java Solution
YouTube video 'Leetcode | 231. Power of Two | Easy | Java Solution'
Developer Docs 4 mins
Leetcode | 231. Power of Two | Easy | Java Solution
YouTube video '231. Power Of Two | Fundamentals | Bit Manipulation | Leetcode'
Coding with Tamilarasan 6 mins
231. Power Of Two | Fundamentals | Bit Manipulation | Leetcode
YouTube video '231. Power of Two | Leetcode Daily - Python'
Leetcode Daily 6 mins
231. Power of Two | Leetcode Daily - Python
YouTube video 'Power of Two | Leetcode 231 | Live coding session 🔥🔥🔥🔥 | Bit Manipulation | 3 Approaches'
Coding Decoded 9 mins
Power of Two | Leetcode 231 | Live coding session 🔥🔥🔥🔥 | Bit Manipulation | 3 Approaches
YouTube video 'Power of Two | Day 8 | [June LeetCoding Challenge] [Leetcode #231] [2020]'
Algorithms Made Easy 7 mins
Power of Two | Day 8 | [June LeetCoding Challenge] [Leetcode #231] [2020]
YouTube video 'Daily Leetcode #1957: Aug 09, 2025 - 231. Power of Two'
Programming Live with Larry 4 mins
Daily Leetcode #1957: Aug 09, 2025 - 231. Power of Two
YouTube video '231. Power of Two || leetcode || easy problem || c++ solution with explanation'
code Explainer 3 mins
231. Power of Two || leetcode || easy problem || c++ solution with explanation
YouTube video '231. Power of Two | Leetcode | Python'
Abdullah Arshed 5 mins
231. Power of Two | Leetcode | Python
YouTube video 'Leetcode 231: Power of Two in Telugu  | Math, Bit manipulation | Python DSA | srkcodes'
Srk Codes 12 mins
Leetcode 231: Power of Two in Telugu | Math, Bit manipulation | Python DSA | srkcodes
20 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

3 similar problems

Solved On The Same Day

5 easy
6 solutions   August 12, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • 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