231. Power of Two
Power of Two (LeetCode 231) is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Bit Manipulation Patterns pattern, in the Bitwise Operations - Power of Two/Four Check subpattern.
How to solve Power of Two
Power of Two is a Power of Two and Four Check problem, part of Bit Manipulation Patterns. Check if number is power of two or four using bitwise operations.
Work towards the solution in these steps:
- Consider how binary representations can help solve problems related to powers of two.
- Recall that powers of two have a unique pattern in their binary form compared to other numbers.
- Think about how many '1' bits appear in the binary representation of a power of two.
The reference solution runs in O(1) time and O(1) space.
The Power of Two solution and editorial walks through the full approach with reference code.
Problem statement
Given an integer n, return true if it is a power of two. Otherwise, return false.
An integer n is a power of two, if there exists an integer x such that n == 2x.
Example 1:
Input: n = 1 Output: true Explanation: 20 = 1
Example 2:
Input: n = 16 Output: true Explanation: 24 = 16
Example 3:
Input: n = 3 Output: false
Constraints:
- -231 <= n <= 231 - 1
Follow up: Could you solve it without loops/recursion?
Topics and companies
Topics: Math, Bit Manipulation, Recursion.
Reported in interviews at Apple.
How to practise Power of Two on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(1) time and O(1) space.
Open Power of Two in the code editor, or read the Power of Two editorial for a worked solution with its approach and complexity analysis.
Where Power of Two sits in the DSA pattern sheet
- Bit Manipulation Patterns pattern guide
- Bitwise Operations - Power of Two/Four Check subpattern
- The full DSA patterns sheet
Problems related to Power of Two
Other problems that use the same Bitwise Operations - Power of Two/Four Check and Bit Manipulation Patterns techniques:
- Number of 1 Bits — Easy, same subpattern
- Reverse Bits — Easy, same subpattern
- Bitwise AND of Numbers Range — Medium, same pattern
- Counting Bits — Easy, same pattern
- Find the Difference — Easy, same pattern
- Minimum Array End — Medium, same pattern
Power of Two FAQ
What is the LeetCode number of Power of Two?
Power of Two is LeetCode problem 231, rated Easy.
What pattern is used to solve Power of Two?
Power of Two is a Power of Two and Four Check problem. It belongs to the Bit Manipulation Patterns pattern, in the Bitwise Operations - Power of Two/Four Check subpattern.
What is the time complexity of Power of Two?
The reference solution runs in O(1) time and O(1) space.
Which companies ask Power of Two?
Power of Two has been reported in interviews at Apple.