Problem Informations

• Problem Index: 1780
• Problem Link: Check if Number is a Sum of Powers of Three
• Topics: Math

Problem Description

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$.

Example 1:

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

Example 2:

Input: n = 91
Output: true
Explanation: 91 = 3^0 + 3^2 + 3^4

Example 3:

Input: n = 21
Output: false

Constraints:

• $1 \leq n \leq 10^7$

Intuition

The problem requires us to determine if a given integer $n$ can be represented as the sum of distinct powers of three. Powers of three are numbers of the form $3^x$ where $x$ is a non-negative integer. The key observation is that each power of three can be thought of as a digit in a base-3 numeral system, where each coefficient is either 0 or 1 (since the coefficients cannot exceed 1 for distinct sums).

This means that if we can decompose $n$ into a form that only uses coefficients of 0 and 1 when $n$ is expressed in base-3, then $n$ can indeed be represented as the sum of distinct powers of three. If, however, any coefficient would need to be 2, it suggests that $n$ cannot be decomposed into distinct powers of three and instead suggests a carry would be needed, which violates the distinctness condition.

Approach

The approach involves checking the base-3 representation of $n$. If $n$ can be expressed entirely with coefficients 0 and 1 in base-3, then it can be represented as a sum of distinct powers of three; otherwise, it cannot.

1. Start with the integer $n$.
2. While $n$ is greater than 0, repeat the following steps:
   • Compute the remainder of $n$ when divided by 3, i.e., $n \mod 3$.
   • If the remainder is 2, immediately return false as it indicates that a coefficient of 2 would be needed in the base-3 representation, violating the distinct sum condition.
   • Otherwise, divide $n$ by 3 to shift to the next higher power of three.
3. If the loop completes without returning false, return true. This suggests that $n$ has been fully reduced with allowable coefficients in base-3, showing it can indeed be represented as a sum of distinct powers of three.

Code

C++

class Solution {
public:
    bool checkPowersOfThree(int n) {
        // Continue the loop while n is greater than 0
        while (n > 0) {
            // If the remainder when n is divided by 3 is 2,
            // then it's impossible to represent n as the sum of distinct powers of three
            if (n % 3 == 2) {
                return false;
            }
            // Reduce n by a factor of 3
            n /= 3;
        }
        // If we complete the loop without returning false,
        // it means n can be represented as the sum of distinct powers of three
        return true;
    }
};

Python

class Solution:
    def checkPowersOfThree(self, n: int) -> bool:
        # Continue the loop while n is greater than 0
        while n > 0:
            # If the remainder when n is divided by 3 is 2,
            # then it's impossible to represent n as the sum of distinct powers of three
            if n % 3 == 2:
                return False
            # Reduce n by a factor of 3
            n //= 3
        # If we complete the loop without returning false,
        # it means n can be represented as the sum of distinct powers of three
        return True

Complexity

• Time complexity: $O(\log_3 n)$ The time complexity of the algorithm is $O(\log_3 n)$ because we divide the number $n$ by 3 in each iteration of the loop. This loop continues until $n$ becomes 0, which takes $\log_3 n$ iterations in the worst-case scenario. Each iteration involves only simple arithmetic operations (modulo and division), which are constant time operations.

• Space complexity: $O(1)$ The space complexity is $O(1)$ because the algorithm uses a constant amount of extra space regardless of the size of the input $n$. Only a few integer variables are used, and their memory allocation does not depend on $n$.