How do you solve Perfect Number on LeetCode?

Perfect Number (LeetCode #507) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(sqrt(n)) time complexity and O(1) space complexity. Key insight: Divisors can be found in pairs, which allows us to reduce the number of checks needed.

What is the brute force solution for Perfect Number?

The brute force approach for Perfect Number is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking all numbers less than 'n' to see if they are divisors and summing them up. If the sum equals 'n', then 'n' is a perfect number. The optimal Optimal Solution approach improves this to O(sqrt(n)).

What algorithm or data structure is used to solve Perfect Number?

Perfect Number uses the following concepts: Math. The recommended patterns to study are: Math (Divisor Pairing), Looping to Square Root.

What are the interview tips for Perfect Number?

Always start with a brute-force solution to demonstrate your understanding of the problem. Be prepared to explain how you can optimize your solution and why that optimization works. Test your code with edge cases, such as the smallest and largest possible inputs.

What are common mistakes when solving Perfect Number?

Not considering the case when 'num' is less than or equal to 1. Forgetting to exclude 'n' itself when summing divisors.

#507

Perfect Number

Easy

MathMath (Divisor Pairing)Looping to Square Root

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(sqrt(n))
Space	O(1)	O(1)

💡

Intuition

Time O(sqrt(n))Space O(1)

Instead of checking all numbers up to 'n', we can check only up to the square root of 'n'. This is because divisors come in pairs, and if 'i' is a divisor, then 'n/i' is also a divisor.

⚙️

Algorithm

5 steps

1Step 1: Initialize a variable 'sum' to 1 (since 1 is a divisor for all numbers).
2Step 2: Loop through all integers 'i' from 2 to the square root of 'n'.
3Step 3: If 'n' is divisible by 'i', add 'i' and 'n/i' to 'sum' (avoid adding 'n' itself).
4Step 4: After the loop, check if 'sum' equals 'n'.
5Step 5: Return true if they are equal, otherwise return false.

solution.py9 lines

1def checkPerfectNumber(num):
2    if num <= 1: return False
3    sum = 1
4    for i in range(2, int(num**0.5) + 1):
5        if num % i == 0:
6            sum += i
7            if i != num // i:
8                sum += num // i
9    return sum == num

ℹ

Complexity note: The time complexity is O(sqrt(n)) because we only loop up to the square root of 'n', significantly reducing the number of iterations. The space complexity is O(1) as we use a constant amount of extra space.

1Divisors can be found in pairs, which allows us to reduce the number of checks needed.
2The sum of divisors excluding the number itself is the key to identifying perfect numbers.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.