【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)。

LeetCode题库地址