1780. Check if Number is a Sum of Powers of Three

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 == 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

Solutions

Solution 1: Mathematical Analysis

We find that if a number \(n\) can be expressed as the sum of several "different" powers of three, then in the ternary representation of \(n\), each digit can only be \(0\) or \(1\).

Therefore, we convert \(n\) to ternary and then check whether each digit is \(0\) or \(1\). If not, then \(n\) cannot be expressed as the sum of several powers of three, and we directly return false; otherwise, \(n\) can be expressed as the sum of several powers of three, and we return true.

The time complexity is \(O(\log_3 n)\), and the space complexity is \(O(1)\).

Python3JavaC++GoTypeScript

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

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

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

func checkPowersOfThree(n int) bool {
    for n > 0 {
        if n%3 > 1 {
            return false
        }
        n /= 3
    }
    return true
}

function checkPowersOfThree(n: number): boolean {
    while (n) {
        if (n % 3 > 1) return false;
        n = Math.floor(n / 3);
    }
    return true;
}

Comments