Skip to main content

342. Power of Four

easy

Decide whether an integer is a power of four. Builds on power-of-two intuition with one extra bit-position check — and a slick mod-3 number-theory shortcut.

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

A power of 4 is a power of 2, so start with n > 0 && (n & (n - 1)) == 0.

Hint 2

But not every power of 2 is a power of 4: only those where the single set bit is at an even position (0, 2, 4, ..., 30).

Hint 3

Use a mask with set bits at all even positions: 0x55555555 = 0101...01 in binary. Power of 4 iff n & 0x55555555 != 0 (in addition to being a power of 2).

Hint 4

Math alternative: a power of 4 satisfies (n - 1) % 3 == 0. Because 4^k = (3 + 1)^k expands to 3*(...) + 1.

Solution approach

Reveal approach

Bit approach: a number is a power of 4 iff it is a power of 2 (exactly one set bit) AND that set bit is at an even position. Combine the two checks: return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) != 0. The mask 0x55555555 has 1s at positions 0, 2, 4, ..., 30. O(1) time and space. Math approach using the identity 4^k mod 3 = 1: return n > 0 && (n & (n - 1)) == 0 && (n - 1) % 3 == 0. Both are interview-grade; the bitmask version is slightly more performant, the mod-3 version is more memorable.

Complexity

Time
O(1)
Space
O(1)

Related patterns

  • bit-manipulation
  • math

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 Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →