Check if Number is a Sum of Powers of Three

medium math ternary base conversion

Problem

Given an integer n, return true if n can be written as the sum of distinct powers of three (3⁰, 3¹, 3², …), each used at most once. Otherwise return false.

Key fact: writing n in base 3 uses each power 3^x a digit-many (0, 1, or 2) times. A sum of distinct powers means every base-3 digit must be 0 or 1 — so the answer is true exactly when no ternary digit is 2.

Inputn = 12

Outputtrue

12 = 3¹ + 3². In base 3, 12 = 110₃ — only 0s and 1s, so it works.

n (1 to 10,000,000)

def checkPowersOfThree(n):
    # Strip n into base-3 digits from least significant up.
    while n > 0:
        if n % 3 == 2:      # a digit of 2 means 3^x used twice
            return False    # not a sum of distinct powers
        n //= 3             # drop this digit, move to next power
    return True             # every digit was 0 or 1

function checkPowersOfThree(n) {
  // Strip n into base-3 digits from least significant up.
  while (n > 0) {
    if (n % 3 === 2) {      // a digit of 2 means 3^x used twice
      return false;         // not a sum of distinct powers
    }
    n = Math.floor(n / 3);  // drop this digit, move to next power
  }
  return true;              // every digit was 0 or 1
}

boolean checkPowersOfThree(int n) {
    // Strip n into base-3 digits from least significant up.
    while (n > 0) {
        if (n % 3 == 2) {   // a digit of 2 means 3^x used twice
            return false;   // not a sum of distinct powers
        }
        n /= 3;             // drop this digit, move to next power
    }
    return true;            // every digit was 0 or 1
}

bool checkPowersOfThree(int n) {
    // Strip n into base-3 digits from least significant up.
    while (n > 0) {
        if (n % 3 == 2) {   // a digit of 2 means 3^x used twice
            return false;   // not a sum of distinct powers
        }
        n /= 3;             // drop this digit, move to next power
    }
    return true;            // every digit was 0 or 1
}

Explanation

Every non-negative integer has exactly one base-3 (ternary) representation, where each position x carries a digit 0, 1, or 2 that counts how many times the power 3^x is added. So n = d₀·3⁰ + d₁·3¹ + d₂·3² + ….

We want to use each power of three at most once. That is possible exactly when every ternary digit is 0 (power skipped) or 1 (power used once). A digit of 2 would mean some 3^x is needed twice, which violates the "distinct" rule — and you cannot fix it, because two of 3^x is still less than 3^x+1, so there is no way to carry it into a single higher power.

The algorithm extracts ternary digits from the least significant end: n % 3 is the current digit and n //= 3 drops it. The moment we see a digit equal to 2, we return false. If we exhaust all digits without seeing a 2, the answer is true.

Example: n = 12 → digits 0, 1, 1 (so 110₃). No 2 appears, so 12 = 3¹ + 3² works. Counter-example: n = 21 → 21 % 3 = 0, 7 % 3 = 1, 2 % 3 = 2 → a 2 appears (210₃), so it returns false.

The hint that the largest power needed is 3¹⁶ follows from the constraint n ≤ 10⁷, since 3¹⁶ ≈ 4.3·10⁷ already exceeds it.

Time: O(log₃ n) Space: O(1)