342. Power of Four
Power of Four (LeetCode 342) 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 Four
Power of Four 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 powers of numbers relate to repeated multiplication and how that might reflect in their binary representation.
- Recall that powers of two have a unique property in binary: only one bit is set to 1.
- Since powers of four are also powers of two, think about additional constraints that separate powers of four from other powers of two.
The reference solution runs in O(1) time and O(1) space.
The Power of Four 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 four. Otherwise, return false.
An integer n is a power of four, if there exists an integer x such that n == 4x.
Example 1:
Input: n = 16 Output: true
Example 2:
Input: n = 5 Output: false
Example 3:
Input: n = 1 Output: true
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 Two Sigma.
How to practise Power of Four 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 Four in the code editor, or read the Power of Four editorial for a worked solution with its approach and complexity analysis.
Where Power of Four 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 Four
Other problems that use the same Bitwise Operations - Power of Two/Four Check and Bit Manipulation Patterns techniques:
- Bitwise AND of Numbers Range — Medium, same subpattern
- Minimum Array End — Medium, same subpattern
- Pow(x, n) — Medium, same subpattern
- Counting Bits — Easy, same pattern
- Find the Difference — Easy, same pattern
- Missing Number — Easy, same pattern
Power of Four FAQ
What is the LeetCode number of Power of Four?
Power of Four is LeetCode problem 342, rated Easy.
What pattern is used to solve Power of Four?
Power of Four 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 Four?
The reference solution runs in O(1) time and O(1) space.
Which companies ask Power of Four?
Power of Four has been reported in interviews at Two Sigma.