⚡Flashcard Drill➔
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

  1. A number is a sum of distinct powers of three exactly when its base-3 representation uses only the digits 0 and 1.
  2. Repeatedly take n % 3: a digit of 2 would require using the same power of three twice, which distinctness forbids.
  3. A digit of 1 means that power is used once, and a digit of 0 means it is omitted; both are fine.
  4. Divide by three and repeat until n becomes zero, at which point every digit was 0 or 1.

💻 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: a 2 means two copies of the same power, violating the distinctness requirement.
  • Checking digits in base 2: the relevant base is 3, not 2.
  • Forgetting to divide by three: the loop would never terminate.
  • Returning n == 0 explicitly: 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.
🎯 Drill This Card Now➔

🧩 Related Math & Geometry Problems