【2022-12-09每日一题】1780. 判断一个数字是否可以表示成三的幂的和[Medium]
2022-12-09
1分钟阅读时长
2022-12-09每日一题：1780. 判断一个数字是否可以表示成三的幂的和
难度：Medium
标签：数学
给你一个整数 n ，如果你可以将 n 表示成若干个不同的三的幂之和，请你返回 true ，否则请返回 false 。
对于一个整数 y ，如果存在整数 x 满足 y == 3x ，我们称这个整数 y 是三的幂。
示例 1：
输入：n = 12 输出：true 解释：12 = 31 + 32
示例 2：
输入：n = 91 输出：true 解释：91 = 30 + 32 + 34
示例 3：
输入：n = 21 输出：false
提示：
1 <= n <= 107
方法一：三进制
思路与算法
我们可以将 n 转换成 3 进制。如果 n 的 3 进制表示中每一位均不为 2，那么答案为 True，否则为 False。
例如当 n=12 时，12=(110)3，满足要求；当 n=21 时，21=(210)3，不满足要求。
代码
//21/3= 7 21%3=0
//7/3 = 2 7%3=1
//2/3 = 0 2%3=2
//210 2*3^2+1*3^1+0*3^0=18+3+0=21
// 出现2次3^2
func checkPowersOfThree(n int) bool {
for ; n > 0; n /= 3 {
if n%3 == 2 {
return false
}
}
return true
}
复杂度分析
- 时间复杂度：O(logn)。
- 空间复杂度：O(1)。