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

🟠   🔖  数学  🔗 力扣 LeetCode

题目

Given an integer n, return true if it is possible to representn as the sum of distinct powers of three. Otherwise, return false.

An integer y is a power of three if there exists an integer x such that y == 3x.

Example 1:

Input: n = 12

Output: true

Explanation: 12 = 31 + 32

Example 2:

Input: n = 91

Output: true

Explanation: 91 = 30 + 32 + 34

Example 3:

Input: n = 21

Output: false

Constraints:

• 1 <= n <= 10^7

题目大意

给你一个整数 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 <= 10^7

解题思路

本题的核心思想是 三进制表示，判断 n 是否可以表示为 若干个不同的 3 的幂之和，即 n 的三进制表示是否只包含 0 和 1。

• 如果 n 在三进制表示中含有 2，则无法由 3 的不同幂之和组成（因为 3^i 只能使用一次）。
• 模拟 3 进制除法：
  • 每次取 n % 3，如果余数为 2，返回 false。
  • 否则，将 n 除以 3，继续判断。

复杂度分析

• 时间复杂度：O(log n)，每次 n 除以 3，最多执行 O(log_3 n) 次。
• 空间复杂度：O(1)，仅使用常数额外空间。

代码

/**
 * @param {number} n
 * @return {boolean}
 */
var checkPowersOfThree = function (n) {
	while (n > 0) {
		if (n % 3 == 2) return false;
		n = (n / 3) | 0;
	}
	return true;
};

相关题目

题号	标题	题解	标签	难度	力扣
326	3 的幂	[✓]	递归 数学	🟢	🀄️ 🔗