NeetCode #917LC-1780MediumMath & Geometry
← Back to All Problems#917 · #1780 · Check if Number is a Sum of Powers of Three(判断一个数字是否可以表示成三的幂的和)
📌 Problem Statement & Constraints
Given an integer
n, return true if it can be written as the sum of distinct powers of three, otherwise false. Constraints: 1 <= n <= 10^7.💡 Core Algorithmic Approaches
- A number is a sum of distinct powers of three exactly when its base-3 representation uses only the digits
0and1. - Repeatedly take
n % 3: a digit of2would require using the same power of three twice, which distinctness forbids. - A digit of
1means that power is used once, and a digit of0means it is omitted; both are fine. - Divide by three and repeat until
nbecomes zero, at which point every digit was0or1.
💻 Benchmark Python3 Implementation
class Solution:
def checkPowersOfThree(self, n: int) -> bool:
while n > 0:
if n % 3 == 2:
return False # would need this power of three twice
n //= 3
return True⚡ Complexity Deep Dive
⏱️ Time Complexity
O(log_3 n): the number of base-3 digits.
💾 Space Complexity
O(1).
⚠️ Interview Pitfalls & Follow-ups
- Allowing the digit
2: a2means two copies of the same power, violating the distinctness requirement. - Checking digits in base 2: the relevant base is
3, not2. - Forgetting to divide by three: the loop would never terminate.
- Returning
n == 0explicitly: reaching zero is the loop's exit condition, and it means the answer is true.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.