# Check if Number is a Sum of Powers of Three
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/check-if-number-is-a-sum-of-powers-of-three)
Canonical: https://scaleengineer.com/dsa/problems/check-if-number-is-a-sum-of-powers-of-three
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
---
## Problem
Given an integer `n`, return `true` _if it is possible to represent_ `n` _as the sum of distinct powers of three._ Otherwise, return `false`.

An integer `y` is a power of three if there exists an integer `x` such that `y == 3x`.

**Example 1:**

**Input:** n = 12
**Output:** true
**Explanation:** 12 = 31 + 32

**Example 2:**

**Input:** n = 91
**Output:** true
**Explanation:** 91 = 30 + 32 + 34

**Example 3:**

**Input:** n = 21
**Output:** false

**Constraints:**

* `1 <= n <= 107`

# Approaches
## Recursive Backtracking (Subset Sum)
This approach treats the problem as a variation of the classic Subset Sum problem. We first generate all powers of three that are less than or equal to `n`. Then, we use a recursive function to explore all possible subsets of these powers to see if any subset sums up to `n`. Since each power can either be included in the sum or not, this leads to a backtracking algorithm that checks all possibilities.
**Time:** O(2^log(n)) - The time complexity is exponential in the number of powers of three, `k`. Since `k` is `log3(n)`, the complexity is `O(2^log3(n))`, which can be rewritten as `O(n^(log3(2)))` or approximately `O(n^0.63)`. This is a polynomial-time complexity. · **Space:** O(log n) - The space is used for storing the powers of three, where there are `k = log3(n)` such powers. The recursion depth also goes up to `k`.
**Pros:** Conceptually straightforward for those familiar with backtracking and recursion.; Guaranteed to find the correct answer by exploring all possibilities.
**Cons:** Inefficient compared to other methods due to its exponential time complexity.; The time complexity, although on a small input size (`log n`), is much worse than logarithmic solutions.
### Explanation
The core idea is to determine if `n` can be formed by a sum of a subset of the available powers of three. We can model this with a recursive function that makes a decision for each power of three: either use it in the sum or don't. This exploration of all possibilities guarantees finding a solution if one exists.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean checkPowersOfThree(int n) {
        List<Integer> powers = new ArrayList<>();
        int p = 1;
        while (p <= n) {
            powers.add(p);
            // Prevent integer overflow before multiplication
            if (p > Integer.MAX_VALUE / 3) {
                break;
            }
            p *= 3;
        }
        // Start recursion from the last element of the list (largest power)
        return canPartition(n, powers, powers.size() - 1);
    }

    private boolean canPartition(int target, List<Integer> powers, int index) {
        // Base case: successful partition
        if (target == 0) {
            return true;
        }
        // Base case: invalid path
        if (target < 0 || index < 0) {
            return false;
        }

        // Recursive step:
        // 1. Try to form the sum including the current power
        if (canPartition(target - powers.get(index), powers, index - 1)) {
            return true;
        }

        // 2. Try to form the sum excluding the current power
        return canPartition(target, powers, index - 1);
    }
}
```
### Algorithm
*   Create a list of all powers of three (1, 3, 9, ...) that are less than or equal to the input `n`.
*   Implement a recursive helper function, say `canPartition(target, powers, index)`.
*   The base cases for the recursion are:
    *   If `target` is 0, it means we have found a valid combination of powers, so return `true`.
    *   If `target` becomes negative or we have exhausted all available powers (`index < 0`), it's impossible to form the sum, so return `false`.
*   In the recursive step, for each power `powers[index]`, we explore two choices:
    *   **Include:** Subtract the current power from the target and recurse on the remaining powers: `canPartition(target - powers.get(index), powers, index - 1)`.
    *   **Exclude:** Keep the target as is and recurse on the remaining powers: `canPartition(target, powers, index - 1)`.
*   If either of these recursive calls returns `true`, it means a valid sum is possible, and we propagate `true` up the call stack.

## Greedy Subtraction
A more efficient approach is to use a greedy strategy. The idea is to try to construct the sum by always picking the largest possible power of three that is less than or equal to the remaining value of `n`. We iterate from the largest possible power of three downwards. If we can reduce `n` to zero this way, then a valid representation exists. This works because the representation of a number in any base is unique, and this greedy subtraction is equivalent to finding the digits of that representation.
**Time:** O(log n) - The loop runs for each power of three less than or equal to `n`. The number of such powers is proportional to `log3(n)`, making the algorithm very fast. · **Space:** O(1) - We only use a few variables to store `n` and the current power of three, regardless of the size of `n`.
**Pros:** Very efficient with logarithmic time complexity.; Uses constant extra space.; The iterative logic is simple to implement and understand.
**Cons:** Requires knowing or calculating the largest power of three to start with, though this is a minor issue for the given constraints.
### Explanation
This greedy algorithm is effective because any power of three, `3^k`, is greater than the sum of all smaller powers of three (`3^0 + 3^1 + ... + 3^(k-1)`). This property ensures that if we skip a power of three when we could have taken it, we can't make up for it with the smaller powers. Therefore, the greedy choice is always optimal.

```java
class Solution {
    public boolean checkPowersOfThree(int n) {
        // 3^14 = 4782969, which is the largest power of 3 <= 10^7
        // 3^15 is too large.
        int powerOf3 = 4782969;

        while (powerOf3 > 0) {
            // If we can subtract the current power of 3, do so.
            if (n >= powerOf3) {
                n -= powerOf3;
            }
            // Move to the next smaller power of 3.
            powerOf3 /= 3;
        }

        // If n is 0, it means it was perfectly represented by a sum of distinct powers of 3.
        return n == 0;
    }
}
```
### Algorithm
*   Determine the largest power of three to start with. For the given constraints (`n <= 10^7`), the largest power needed is `3^14 = 4,782,969`.
*   Initialize a variable, say `powerOf3`, with this value.
*   Iterate downwards as long as `powerOf3 > 0`.
*   In each iteration, check if the current `n` is greater than or equal to `powerOf3`.
    *   If it is, subtract `powerOf3` from `n`. This signifies that we are using this power of three in our sum.
*   After checking, update `powerOf3` to the next smaller power by dividing it by 3.
*   After the loop finishes, if `n` has been reduced to exactly 0, it means `n` was successfully represented as a sum of distinct powers of three. Return `true`.
*   Otherwise, return `false`.

## Ternary (Base-3) Representation
This is the most elegant and insightful approach. The problem is equivalent to checking the ternary (base-3) representation of the number `n`. A number can be written as a sum of *distinct* powers of three if and only if its representation in base 3 consists only of the digits 0 and 1. For example, `12` in base 10 is `110` in base 3 (`1*3^2 + 1*3^1 + 0*3^0`), so it's a sum of distinct powers. However, `21` in base 10 is `210` in base 3 (`2*3^2 + 1*3^1 + 0*3^0`). The digit `2` implies that `3^2` is needed twice (`2 * 3^2 = 3^2 + 3^2`), which violates the "distinct powers" condition.
**Time:** O(log n) - The number of iterations in the while loop is equal to the number of digits in the base-3 representation of `n`, which is `floor(log3(n)) + 1`. · **Space:** O(1) - The algorithm uses only a constant amount of extra space for the input variable `n`.
**Pros:** Extremely efficient in both time and space.; Very concise and elegant code.; Directly addresses the mathematical nature of the problem without any pre-computation or data structures.
**Cons:** Requires the mathematical insight connecting the problem to number bases, which might not be immediately obvious to everyone.
### Explanation
The algorithm to check the base-3 digits is simple. We can extract the digits one by one from least significant to most significant by repeatedly taking the number modulo 3 and then dividing by 3. If we ever encounter a digit of 2, we know the condition is not met.

```java
class Solution {
    public boolean checkPowersOfThree(int n) {
        // Keep checking the number until it becomes 0
        while (n > 0) {
            // The remainder when dividing by 3 gives the last digit in base-3.
            // If this digit is 2, it's not a sum of *distinct* powers of 3.
            if (n % 3 == 2) {
                return false;
            }
            // Move to the next digit by dividing by 3.
            n /= 3;
        }
        // If we went through all the digits and none were 2, the number is valid.
        return true;
    }
}
```
### Algorithm
*   Start a loop that continues as long as `n > 0`.
*   Inside the loop, calculate the remainder when `n` is divided by 3 (`n % 3`). This remainder is the next digit in the base-3 representation of `n`.
*   If the remainder is 2, it's impossible to represent `n` as a sum of distinct powers of three. Return `false` immediately.
*   If the remainder is 0 or 1, the condition is not violated, so we continue.
*   Update `n` for the next iteration by performing integer division: `n = n / 3`.
*   If the loop completes (meaning `n` has become 0), it implies we never found a remainder of 2. Therefore, all base-3 digits were 0 or 1, and we can return `true`.

# Solutions
### Java

```java
class Solution { public boolean checkPowersOfThree ( int n ) { while ( n > 0 ) { if ( n % 3 > 1 ) { return false ; } n /= 3 ; } return true ; } }
```

### CPP

```cpp
class Solution { public: bool checkPowersOfThree ( int n ) { while ( n ) { if ( n % 3 > 1 ) return false ; n /= 3 ; } return true ; } };
```

### Python

```python
class Solution : def checkPowersOfThree ( self , n : int ) -> bool : while n : if n % 3 > 1 : return False n //= 3 return True
```