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 Sam K., 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

More Bit Manipulation practice problems

See all Bit Manipulation problems →