Perfect Number

Problem Statement

In mathematical terms, a perfect number is a positive integer that matches the sum of its positive divisors, excluding the integer itself. For clarification, a divisor is any number that can evenly divide the integer in question without leaving a remainder.

The task at hand involves developing a function that takes an integer n as an input. The function should determine whether n is a perfect number. If n qualifies as a perfect number, the function should return true, otherwise, it should return false.

Examples

Example 1

Input:

num = 28

Output:

true

Explanation:

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

Example 2

Input:

num = 7

Output:

false

Constraints

• 1 <= num <= 108

Approach and Intuition

To solve the problem of identifying perfect numbers, let's analyze the given examples and constraints:

Guiding Principles:

1. Understand that a perfect number is equal to the sum of its proper divisors other than itself.
2. Key challenge: Efficiently summing up the divisors without iterating up to the number itself, as this would not be performant especially near the upper limit of our constraint (10^8).

Breaking Down the Examples:

• Example 1:

  • For num = 28, the divisors (excluding 28 itself) are 1, 2, 4, 7, and 14.
  • Adding these divisors gives 1 + 2 + 4 + 7 + 14 = 28, which matches the number itself, confirming that 28 is a perfect number.

• Example 2:

  • For num = 7, the only divisors excluding 7 are 1.
  • Summing these gives 1, which isn’t equal to 7, meaning 7 is not a perfect number.

By leveraging the properties of divisors and focusing on efficiency (not checking beyond the square root of the number), this approach ensures that we can reliably determine if a number is perfect without excessive computations, adhering to the constraints provided.

Solutions

public class Solution {
    public int perfectNumFormula(int prime) {
        return (1 << (prime - 1)) * ((1 << prime) - 1);
    }
    public boolean checkPerfectNumber(int num) {
        int[] primeList = new int[]{2, 3, 5, 7, 13, 17, 19, 31};
        for (int prime : primeList) {
            if (perfectNumFormula(prime) == num)
                return true;
        }
        return false;
    }
}