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

题目描述

这是 LeetCode 上的 1780. 判断一个数字是否可以表示成三的幂的和 ,难度为 中等

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

对于一个整数 y,如果存在整数 x 满足 y == 3x,我们称这个整数 y 是三的幂。

示例 1:

1
2
3
4
5
输入:n = 12

输出:true

解释:12 = 31 + 32

示例 2:
1
2
3
4
5
输入:n = 91

输出:true

解释:91 = 30 + 32 + 34

示例 3:
1
2
3
输入:n = 21

输出:false

提示:

  • $1 <= n <= 10^7$

数学

这是一道考察「进制转换」基本认识的题目。

n 看作一个三进制数,例如对于 $(210)_{3}$ 而言,其代表的是 $2 \times 3^2 + 1 \times 3^1 + 0 \times 3^0$ 十进制数。

由于题目规定组成和的三的幂需要满足「不同」的条件,因此 n 所代表的三进制表示中的系数只能是 $1$ 或 $0$,而不是能是 $2$。

Java 代码:

1
2
3
4
5
6
7
8
9
class Solution {
public boolean checkPowersOfThree(int n) {
while (n != 0) {
if (n % 3 == 2) return false;
n /= 3;
}
return true;
}
}

TypeScript 代码:
1
2
3
4
5
6
7
function checkPowersOfThree(n: number): boolean {
while (n != 0) {
if (n % 3 == 2) return false
n = Math.floor(n / 3)
}
return true
}

Python 代码
1
2
3
4
5
6
7
class Solution:
def checkPowersOfThree(self, n: int) -> bool:
while n != 0:
if n % 3 == 2:
return False
n //= 3
return True

  • 时间复杂度:$O(\log{n})$
  • 空间复杂度:$O(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1780 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。