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
Hint 1
Write
nin base 3 and look at its digits.Hint 2
Using a power at most once means every base-3 digit must be 0 or 1.
Hint 3
So the answer is
falseexactly 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
- Repeatedly take
n % 3. - If the remainder is 2, the representation needs that power twice — return
false. - Otherwise divide
nby 3 and continue. - Return
trueoncenreaches 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
nis 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 TrueJava
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.