We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Perfect Number

Number: 507

Difficulty: Easy

Paid? No

Companies: Grammarly, Google, Meta, Microsoft, Amazon, Accenture, Fallible

Problem Description

Determine if a given positive integer n is a perfect number. A perfect number is one that equals the sum of its positive divisors, excluding itself.

Key Insights

  • Only need to consider divisors up to the square root of n to efficiently find all proper divisors.
  • For each divisor found, include both the divisor and its complement (n divided by the divisor) if they are distinct.
  • Edge case: When n is 1, it cannot be a perfect number.

Space and Time Complexity

Time Complexity: O(√n) – The loop iterates up to the square root of n. Space Complexity: O(1) – Constant extra space is used.

Solution

We start by handling the edge case where n equals 1; in this case, return false because 1 does not have any proper divisors besides itself. For any n greater than 1, we initialize the sum of divisors with 1 (since 1 is a proper divisor of all numbers). We then iterate from 2 to the square root of n. If a number i divides n, it is a divisor. We then add both i and n/i if they are different. If n is a perfect square, take care not to add the square root twice. Finally, after summing all proper divisors, we check if the sum equals n.

Code Solutions

# Python solution with line-by-line comments
def checkPerfectNumber(n):
    # Edge case: if n is 1, it cannot be a perfect number.
    if n == 1:
        return False
    # Start with 1 as a divisor for any n > 1.
    divisor_sum = 1
    # Iterate from 2 to sqrt(n)
    i = 2
    while i * i <= n:
        if n % i == 0:
            # Add the divisor
            divisor_sum += i
            # Add the complement divisor if it's different
            if i != n // i:
                divisor_sum += n // i
        i += 1
    # Check if the sum of divisors equals the number itself.
    return divisor_sum == n

# Testing the function
print(checkPerfectNumber(28))  # Expected output: True
print(checkPerfectNumber(7))   # Expected output: False
← Back to All Questions