What is the best approach to solve the Power of Three problem?

The most efficient approach is to use logarithms, but iterative or recursive methods are also valid solutions depending on interview constraints.

How do I handle edge cases in the Power of Three problem?

Ensure that you account for negative numbers, zero, and other non-positive values, which cannot be powers of three.

What is the time complexity of the Power of Three problem?

The time complexity is O(log n) for both recursive and iterative approaches, while the logarithmic method can achieve O(1) time complexity.

Can I use recursion to solve this problem?

Yes, recursion is a valid approach. It checks if n is divisible by 3 and continues to divide it until reaching 1 or an invalid state.

What should I focus on during the interview for the Power of Three problem?

Focus on demonstrating a clear understanding of recursion and math principles, and be mindful of handling edge cases efficiently.

#326

Easy

auto_awesome数学·递归

LeetCode 题解工作台

3 的幂

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3 x 示例 1：输入： n = 27 输出： true 示例 2：输入： n = 0 输出： false 示例 3：输入…

数学递归

题目描述

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3^x

示例 1：

输入：n = 27
输出：true

示例 2：

输入：n = 0
输出：false

示例 3：

输入：n = 9
输出：true

示例 4：

输入：n = 45
输出：false

提示：

-2³¹ <= n <= 2³¹ - 1

进阶：你能不使用循环或者递归来完成本题吗？

lightbulb

解题思路

方法一：试除法

如果 $n \gt 2$ ，我们可以不断地将 $n$ 除以 $3$ ，如果不能整除，说明 $n$ 不是 $3$ 的幂，否则继续除以 $3$ ，直到 $n$ 小于等于 $2$ 。如果 $n$ 等于 $1$ ，说明 $n$ 是 $3$ 的幂，否则不是 $3$ 的幂。

时间复杂度 $O(\log_3n)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        while n > 2:
            if n % 3:
                return False
            n //= 3
        return n == 1

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Evaluate the candidate's understanding of recursion and iteration.
question_mark
Check if the candidate can efficiently apply math concepts to solve the problem.
question_mark
Observe how the candidate handles edge cases like negative numbers and 0.

warning

常见陷阱

外企场景

error
Not handling negative numbers or zero correctly, which can lead to incorrect answers.
error
Overcomplicating the solution with unnecessary computations when a simpler method exists.
error
Failing to optimize for large values of n or introducing unnecessary space complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Check if n is a power of two instead of three.
arrow_right_alt
Check if n is a power of an arbitrary integer (other than 3).
arrow_right_alt
Implement the solution in a language with different recursion limits.

help

常见问题

外企场景

继续练习

#342 4的幂 #273 整数转换英文表示 #390 消除游戏