Check if Number is a Sum of Powers of Three

Medium
547.

Check if Number is a Sum of Powers of Three

Check if Number is a Sum of Powers of Three is a medium coding problem on math and number theory, asked in Amazon and Google interviews.

Given an integer n, return true if it can be written as the sum of distinct powers of three.

A power of three is 3^i for some integer i >= 0.

Example 1

Input
n = 12
Output
true
Explanation
12 = 3 + 9 = 3^1 + 3^2.

Example 2

Input
n = 91
Output
true
Explanation
91 = 1 + 9 + 81 = 3^0 + 3^2 + 3^4.

Example 3

Input
n = 21
Output
false

Constraints

  • 1 <= n <= 10000000
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 checkPowersOfThree = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Check if Number is a Sum of Powers of Three — Solution

Check if Number is a Sum of Powers of Three solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Check if Number is a Sum of Powers of Three is a medium coding problem on math and number theory, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Math, Number Theory
  • Asked at: Amazon, Google
  • 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 can be written as the sum of distinct powers of three.

A power of three is 3^i for some integer i >= 0.

Example 1

Input: n = 12
Output: true
Explanation: 12 = 3 + 9 = 3^1 + 3^2.

Example 2

Input: n = 91
Output: true
Explanation: 91 = 1 + 9 + 81 = 3^0 + 3^2 + 3^4.

Example 3

Input: n = 21
Output: false

Constraints

  • 1 <= n <= 10000000

Hints for Check if Number is a Sum of Powers of Three

  1. Hint 1

    Write n in base 3 and look at its digits.

  2. Hint 2

    Using a power at most once means every base-3 digit must be 0 or 1.

  3. Hint 3

    So the answer is false exactly when some base-3 digit is 2.

How to solve Check if Number is a Sum of Powers of Three

A sum of distinct powers of three is precisely a number whose base-3 representation uses only the digits 0 and 1 — the same way a sum of distinct powers of two is any number in binary.

Approach

  1. Repeatedly take n % 3.
  2. If the remainder is 2, the representation needs that power twice — return false.
  3. Otherwise divide n by 3 and continue.
  4. Return true once n reaches 0.

Why it works

Base-3 representations are unique, so if any digit is 2 there is no way to rewrite the number using each power at most once. Conversely, a representation of only 0s and 1s is a sum of distinct powers.

Complexity

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

Pitfalls

  • A greedy subtraction of the largest power also works, but only because the digits are unique — it is easy to implement incorrectly.
  • The loop must run until n is 0, not stop at the first non-zero remainder.

Reference solution

Python

def checkPowersOfThree(n: int) -> bool:
    while n > 0:
        if n % 3 == 2:
            return False
        n //= 3
    return True

Java

public static boolean checkPowersOfThree(int n) {
    while (n > 0) {
        if (n % 3 == 2) return false;
        n /= 3;
    }
    return true;
}

C++

bool checkPowersOfThree(int n) {
    while (n > 0) {
        if (n % 3 == 2) return false;
        n /= 3;
    }
    return true;
}

JavaScript

var checkPowersOfThree = function(n) {
    while (n > 0) {
        if (n % 3 === 2) return false;
        n = Math.floor(n / 3);
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue