Skip to main content

342. Power of Four

easy

Check whether a number is a power of four. Extends the power-of-two bit-trick with one extra constraint: the single set bit must sit at an even position.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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 == 4^x.

Constraints

  • -2^31 <= n <= 2^31 - 1

Examples

Example 1

Input
n = 16
Output
true

Example 2

Input
n = 5
Output
false

Example 3

Input
n = 1
Output
true

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Every power of four is a power of two, so first check (n & (n - 1)) == 0 and n > 0.

Hint 2

Among powers of two, which are also powers of four? Look at the bit positions: 1, 4, 16, 64, ... — the single set bit is always at an even index.

Hint 3

Build a mask covering all even bit positions: 0x55555555. A power-of-four has its single bit inside that mask.

Solution approach

Reveal approach

Two-condition check. Return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) != 0. First condition: n is a power of two (exactly one set bit). Second condition: that bit lies at an even position. The mask 0x55555555 in binary is 01010101...01 (bit 0, 2, 4, ... set), so AND'ing with it isolates bits at even indices. A power of four hits one of those even positions; a power of two that isn't a power of four (e.g., 2, 8, 32) hits an odd position and zeros out. O(1) time, O(1) space.

Complexity

Time
O(1)
Space
O(1)

Related patterns

  • bit-manipulation

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Two Sigma

Practice these live with InterviewChamp.AI

Drill Power of Four and Bit Manipulation problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →