『LeetCode』1780 判断一个数字是否可以表示成三的幂的和

题目

1780. 判断一个数字是否可以表示成三的幂的和

给你一个整数 n ，如果你可以将 n 表示成若干个不同的三的幂之和，请你返回 true ，否则请返回 false 。

对于一个整数 y ，如果存在整数 x 满足 \(y == 3^{x}\) ，我们称这个整数 y 是三的幂。

示例 1：

输入：n = 12
输出：true
解释：12 = 3^{1} + 3^{2}

示例 2：

输入：n = 91
输出：true
解释：91 = 3^{0} + 3^{2} + 3^{4}

示例 3：

输入：n = 21
输出：false

提示：

\(1 <= n <= 10^{7}\)

题解

【判断一个数字是否可以表示成三的幂的和】简单枚举

枚举&贪心

仿照二进制的方法由大到小枚举即可

可行性分析，首先题目有先决条件：若干个不同的三的幂之和

所以关键问题是假设存在 \(3^x < n\) ，那么是否存在 \(\sum_i 3^i = n, i < x\), 结论显然是否定的，因为有 \(\sum\limits_{i=0}^{x - 1} 3 ^ i < 3^x\) ,故不存在 \(\sum_i 3^i = n, i < x\)，所以贪心策略是可行的

# Code language: Python
class Solution:
    def checkPowersOfThree(self, n: int) -> bool:
        base = 3
        while base * 3 <= n:
            base *= 3
        while base:
            if n >= base:
                n -= base
            base //= 3
        return n == 0

// Code language: Java
class Solution {
    public boolean checkPowersOfThree(int n) {
        long base = 1, t = n;
        while (base * 3 <= t) base *= 3;
        while (base > 0) {
            if (t >= base) t -= base;
            base /= 3;
        }
        return t == 0;
    }
}

// Code language: C++
class Solution {
public:
    bool checkPowersOfThree(int n) {
        long long base = 1, t = n;
        while (base * 3 <= t) base *= 3;
        while (base > 0) {
            if (t >= base) t -= base;
            base /= 3;
        }
        return t == 0;
    }
};

/* Code language: JavaScript */
/**
 * @param {number} n
 * @return {boolean}
 */
var checkPowersOfThree = function(n) {
    var base = 1;
    while (base * 3 <= n) base *= 3;
    while (base > 0) {
        if (n >= base) n -= base;
        base /= 3;
    }
    return n == 0;
};

时间复杂度: \(O(\log n)\)
空间复杂度: \(O(1)\)

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』1780 判断一个数字是否可以表示成三的幂的和

题目

标签

题解

枚举&贪心