Power of Three

Easy
155.

Power of Three

Power of Three is an easy coding problem on math and recursion, asked in Amazon, Google and Hulu interviews.

Given an integer n, return true if it is a power of three — that is, if there exists an integer x with n == 3^x.

Example 1

Input
n = 27
Output
true
Explanation
3^3 = 27.

Example 2

Input
n = 0
Output
false

Example 3

Input
n = 45
Output
false
Explanation
45 = 3² × 5.

Constraints

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

Follow-up: Can you solve it without loops 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 isPowerOfThree = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

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

Power of Three is an easy coding problem on math and recursion, asked in Amazon, Google and Hulu interviews.

  • Difficulty: Easy
  • Topics: Math, Recursion
  • Asked at: Amazon, Google, Hulu
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an integer n, return true if it is a power of three — that is, if there exists an integer x with n == 3^x.

Example 1

Input: n = 27
Output: true
Explanation: 3^3 = 27.

Example 2

Input: n = 0
Output: false

Example 3

Input: n = 45
Output: false
Explanation: 45 = 3² × 5.

Constraints

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

Follow-up: Can you solve it without loops or recursion?

Hints for Power of Three

  1. Hint 1

    The loop solution divides by 3 while the remainder is zero and checks that 1 is left.

  2. Hint 2

    Three is prime, so the only divisors of 3^19 that are themselves powers of three are 3^0 … 3^19.

  3. Hint 3

    3^19 = 1162261467 is the largest power of three inside a 32-bit int — test whether it is divisible by n.

How to solve Power of Three

Three is prime, so every divisor of 3^19 — the largest power of three that fits in a 32-bit int — is itself a power of three. Test whether 1162261467 % n == 0.

Approach

  1. Return false for n <= 0.
  2. Return 1162261467 % n == 0.

Why it works

By unique factorisation the divisors of 3^19 are exactly 3^0, 3^1, …, 3^19. Every positive power of three within int range is in that list, and any number with another prime factor cannot divide 3^19.

Complexity

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

Pitfalls

  • This trick works only because 3 is prime — 4^k divides 4^15 but so does 2.
  • Dividing by 3 in a loop while the remainder is zero and checking for 1 is the portable version if you cannot remember the constant.

Reference solution

Python

def isPowerOfThree(n: int) -> bool:
    return n > 0 and 1162261467 % n == 0

Java

public static boolean isPowerOfThree(int n) {
    return n > 0 && 1162261467 % n == 0;
}

C++

bool isPowerOfThree(int n) {
    return n > 0 && 1162261467 % n == 0;
}

JavaScript

var isPowerOfThree = function(n) {
    return n > 0 && 1162261467 % n === 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: Recursion