What is the optimal time complexity for solving the Perfect Number problem?

The optimal time complexity is O(sqrt(n)), where n is the number being checked for perfection.

How do I find divisors for a number efficiently?

To find divisors efficiently, iterate through numbers from 1 to sqrt(n), checking both i and n/i for each valid divisor.

What should I do if my solution is too slow for large inputs?

Optimize the solution by limiting divisor checks to sqrt(n), and avoid unnecessary iterations.

How do I handle edge cases for small numbers like 1?

For n = 1, return false, as 1 has no divisors other than itself, so it’s not a perfect number.

Can the Perfect Number problem be generalized to other types of numbers?

Yes, you can generalize the problem to find other types of numbers based on divisor sums, such as abundant or deficient numbers.

#507

Easy

auto_awesome数学·driven

LeetCode 题解工作台

完美数

对于一个正整数，如果它和除了它自身以外的所有正因子之和相等，我们称它为「完美数」。给定一个整数 n ，如果是完美数，返回 true ；否则返回 false 。示例 1：输入： num = 28 输出： true 解释： 28 = 1 + 2 + 4 + 7 + 14 1, 2,…

数学

题目描述

对于一个 正整数，如果它和除了它自身以外的所有 正因子 之和相等，我们称它为 「完美数」。

给定一个整数 n，如果是完美数，返回 true；否则返回 false。

示例 1：

输入：num = 28
输出：true
解释：28 = 1 + 2 + 4 + 7 + 14
1, 2, 4, 7, 和 14 是 28 的所有正因子。

示例 2：

输入：num = 7
输出：false

提示：

1 <= num <= 10⁸

lightbulb

解题思路

方法一：枚举

我们首先判断 $\textit{num}$ 是否为 1，如果为 1，则 $\textit{num}$ 不是完美数，返回 $\text{false}$ 。

然后，我们从 2 开始枚举 $\textit{num}$ 的所有正因子，如果 $\textit{num}$ 能被 $\textit{num}$ 的某个正因子 $i$ 整除，那么我们将 $i$ 加入到答案 $\textit{s}$ 中。如果 $\textit{num}$ 除以 $i$ 得到的商不等于 $i$ ，我们也将 $\textit{num}$ 除以 $i$ 得到的商加入到答案 $\textit{s}$ 中。

最后，我们判断 $\textit{s}$ 是否等于 $\textit{num}$ 即可。

时间复杂度 $O(\sqrt{n})$ ，其中 $n$ 为 $\textit{num}$ 的大小。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        if num == 1:
            return False
        s, i = 1, 2
        while i <= num // i:
            if num % i == 0:
                s += i
                if i != num // i:
                    s += num // i
            i += 1
        return s == num

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
The candidate efficiently uses the math-driven approach to check divisors.
question_mark
The solution avoids unnecessary loops and optimizes divisor checks.
question_mark
The candidate applies the square root optimization for improved performance.

warning

常见陷阱

外企场景

error
Forgetting to exclude the number itself from the sum of divisors.
error
Not optimizing by checking divisors only up to sqrt(n).
error
Handling large numbers without considering time and space efficiency.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Check for perfect numbers in a range of numbers, not just a single number.
arrow_right_alt
Return the smallest perfect number in a given range.
arrow_right_alt
Extend the problem to find perfect numbers for larger constraints, such as n up to 10^9.

help

常见问题

外企场景

继续练习

#509 斐波那契数 #504 七进制数 #497 非重叠矩形中的随机点