LeetCode 题解工作台
判断一个数字是否可以表示成三的幂的和
给你一个整数 n ，如果你可以将 n 表示成若干个不同的三的幂之和，请你返回 true ，否则请返回 false 。 对于一个整数 y ，如果存在整数 x 满足 y == 3 x ，我们称这个整数 y 是三的幂。 示例 1： 输入： n = 12 输出： true 解释： 12 = 3 1 + 3 …
1
题型
7
代码语言
3
相关题
当前训练重点
中等 · 数学·driven
答案摘要
我们发现，如果一个数 可以表示成若干个“不同的”三的幂之和，那么 的三进制表示中，每一位上的数字只能是 或者 。 因此，我们将 转换成三进制，然后判断每一位上的数字是否是 或者 。如果不是，那么 就不可以表示成若干个三的幂之和，直接返回 ；否则 可以表示成若干个三的幂之和，返回 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·driven 题型思路
题目描述
给你一个整数 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
解题思路
方法一：数学分析
我们发现，如果一个数 可以表示成若干个“不同的”三的幂之和，那么 的三进制表示中，每一位上的数字只能是 或者 。
因此，我们将 转换成三进制，然后判断每一位上的数字是否是 或者 。如果不是，那么 就不可以表示成若干个三的幂之和，直接返回 ；否则 可以表示成若干个三的幂之和，返回 。
时间复杂度 ，空间复杂度 。
class Solution:
def checkPowersOfThree(self, n: int) -> bool:
while n:
if n % 3 > 1:
return False
n //= 3
return True
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(\log_3{n}) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
A candidate demonstrates proficiency in using base conversions to solve a mathematical problem.
- question_mark
The ability to recognize properties of powers of three is evident.
- question_mark
A clean solution without extraneous space or complex data structures is provided.
常见陷阱
外企场景- error
Using an inefficient approach by brute-forcing through combinations of powers of three.
- error
Misunderstanding the base conversion process, especially interpreting digits other than 0 or 1.
- error
Not realizing that only powers of three, not arbitrary numbers, contribute to the sum.
进阶变体
外企场景- arrow_right_alt
Instead of checking for distinct sums, you could modify the problem to check for sums with repeated powers of three.
- arrow_right_alt
This problem can also be extended to powers of other numbers, not just three.
- arrow_right_alt
You could explore a recursive solution that constructs sums from powers of three rather than using the base conversion approach.