#507

Easy

auto_awesomeMath-driven solution strategy

LeetCode Problem Workspace

Perfect Number

Check if a given number is a perfect number by verifying if it's equal to the sum of its divisors, excluding itself.

Problem Statement

A perfect number is a positive integer that is equal to the sum of its proper divisors, excluding the number itself. A divisor of a number n is an integer that divides n without leaving a remainder.

Given a positive integer n, return true if n is a perfect number, and false otherwise. For example, for n = 28, the divisors are 1, 2, 4, 7, and 14, which sum to 28, making it a perfect number.

Examples

Example 1

Input: num = 28

Output: true

28 = 1 + 2 + 4 + 7 + 14 1, 2, 4, 7, and 14 are all divisors of 28.

Example 2

Input: num = 7

Output: false

Example details omitted.

Constraints

1 <= num <= 108

Solution Approach

Identify divisors up to sqrt(n)

To efficiently check if a number is perfect, iterate through all numbers from 1 to the square root of n. For each divisor i, also check if n/i is a divisor and add both to the sum of divisors, excluding n itself.

Optimize with divisor sum comparison

Sum the divisors of n and compare the sum to n itself. If they are equal, return true, indicating the number is perfect. Otherwise, return false.

Avoid unnecessary calculations

Avoid iterating through all numbers up to n by limiting the divisor checks to the square root of n. This reduces time complexity and enhances performance, especially for larger numbers.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this solution is O(sqrt(n)), as we only check divisors up to the square root of n. The space complexity is O(1), as the solution requires constant space for the calculations.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Enumeration

First, we check if $\textit{num}$ is 1. If it is, then $\textit{num}$ is not a perfect number, and we return $\text{false}$.

1

2

3

4

5

6

7

8

9

10

11

12

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

Continue Practicing

#509 fibonacci number #504 base 7 #497 random point in non overlapping rectangles