Power of Four

Easy
413.

Power of Four

EasyMathBit ManipulationRecursionAmazonMicrosoftAdobeTwo Sigma

Power of Four is an easy coding problem on math, bit manipulation and recursion, asked in Amazon, Microsoft, Adobe and Two Sigma interviews.

Given an integer n, return true if it is a power of four — that is, if n == 4^x for some integer x >= 0.

Example 1

Input
n = 16
Output
true

Example 2

Input
n = 5
Output
false

Example 3

Input
n = 1
Output
true

Constraints

  • -2147483648 <= n <= 2147483647

Follow-up: Can you decide it without any loop or recursion?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {boolean}
 */
var isPowerOfFour = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in
AI InterviewGet started

Power of Four — Solution in Python, Java & C++

Power of Four solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Power of Four is an easy coding problem on math, bit manipulation and recursion, asked in Amazon, Microsoft, Adobe and Two Sigma interviews.

Problem statement

Given an integer n, return true if it is a power of four — that is, if n == 4^x for some integer x >= 0.

Example 1

Input: n = 16
Output: true

Example 2

Input: n = 5
Output: false

Example 3

Input: n = 1
Output: true

Constraints

  • -2147483648 <= n <= 2147483647

Follow-up: Can you decide it without any loop or recursion?

Hints for Power of Four

  1. Hint 1

    A power of four is first of all a power of two: positive with exactly one set bit, which n & (n - 1) == 0 tests.

  2. Hint 2

    Among powers of two, the powers of four are the ones whose single bit sits at an even position.

  3. Hint 3

    Mask with 0x55555555, which has all the even-position bits set.

How to solve Power of Four

A power of four is a power of two whose single bit sits at an even position; mask with 0x55555555.

Approach

  1. Require n > 0 and n & (n - 1) == 0.
  2. Require n & 0x55555555 != 0.

Why it works

4^x = 2^(2x), so the single set bit is at an even index; 0x55555555 has exactly the even-index bits set.

Complexity

  • Time — O(1)
  • Space — O(1)

Pitfalls

  • (n - 1) % 3 == 0 is the arithmetic alternative for the even-position test.

Reference solution

Python

def isPowerOfFour(n: int) -> bool:
    return n > 0 and (n & (n - 1)) == 0 and (n & 0x55555555) != 0

Java

public static boolean isPowerOfFour(int n) {
    return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) != 0;
}

C++

bool isPowerOfFour(int n) {
    return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) != 0;
}

JavaScript

var isPowerOfFour = function(n) {
    return n > 0 && (n & (n - 1)) === 0 && (n & 0x55555555) !== 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Bit Manipulation · Recursion