Check if Number is a Sum of Powers of Three

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 == 3^x.

Examples

Example 1:

Input: n = 12
Output: true
Explanation: 12 = 3^1 + 3^2

Example 2:

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

Example 3:

Input: n = 21
Output: false

Constraints:

• 1 <= n <= 10^7

Solution

Method 1 - Maths

The task is to determine if the given integer n can be expressed as the sum of distinct powers of three. A key observation here is that powers of three are unique and non-overlapping when added (e.g., (3^0 = 1), (3^1 = 3), (3^2 = 9), etc.).

Approach

1. Start by generating all possible powers of three that are less than or equal to n.
2. Check if n can be decomposed into these powers of three by greedily subtracting the largest powers of three from n as long as n is non-negative.
3. If n becomes zero after this process, it is possible to represent n as the sum of distinct powers of three, and the result is True. Otherwise, return False.

The approach leverages the unique representation of numbers in base 3. If a number n can be expressed as a sum of distinct powers of three, it essentially means that n, in base 3, should have only digits 0 or 1, as each power of three can be used at most once.

Code

Java

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

Python

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

Complexity

• ⏰ Time complexity: O(log n). Each iteration reduces n significantly since the powers of three grow exponentially. The number of iterations is proportional to ( \log_3(n) ) or ( O(\log n) ) in terms of time complexity.
• 🧺 Space complexity: O(1). The space used is constant as no additional data structures are required to hold intermediate results.

Method 2 - Backtracking

One of the simplest way to solve it will be using backtracking.al

graph TD
    A[0, 1] --> B[1, 3] & C[0,3]

    B --> D[4, 9]  
    B --> E[1, 9]  
    C --> F[3, 9]  
    C --> G[0, 9]  

    D --> H[13, 27] 
    D --> I[4, 27]  
    E --> J[10, 27] 
    E --> K[1, 27]  
    F --> L[12, 27]  
    F --> M[3, 27]  
    G --> N[9, 27]  
    G --> O[0, 27]  

    H["False"]
    I["False"]
    J["False"]
    K["False"]
    L["True"]
    M["False"]
    N["False"]
    O["False"]

Code

Java

class Solution {
    public boolean checkPowersOfThree(int n) {
        return backtrack(0, 1, n);
    }
    
    private boolean backtrack(int currSum, int power, int target) {
        // Base Case: If the current sum equals the target, return true
        if (currSum == target) {
            return true;
        }
        
        // If the current sum exceeds the target or all powers are exhausted, return false
        if (currSum > target || power > target) {
            return false;
        }
        
        // Recursive Case: 
        // (1) Include the current power
        // (2) Skip the current power
        return backtrack(currSum + power, power * 3, target) || backtrack(currSum, power * 3, target);
    }
}

Python

class Solution:
    def checkPowersOfThree(self, n: int) -> bool:
        def backtrack(curr_sum: int, power: int) -> bool:
            # Base Case: If current sum equals the target, return True
            if curr_sum == n:
                return True
            
            # If current sum exceeds the target or power surpasses n, return False
            if curr_sum > n or power > n:
                return False
            
            # Recursive Case:
            # (1) Include the current power
            # (2) Skip the current power
            return backtrack(curr_sum + power, power * 3) or backtrack(curr_sum, power * 3)
        
        return backtrack(0, 1)

Complexity

• ⏰ Time complexity: O(2^k), where k is the number of powers of three less than or equal to target.
• 🧺 Space complexity: O(k). The space complexity arises from the recursion stack, where the depth corresponds to the total number of powers of three (k).