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 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

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

More Math practice problems

See all Math problems →