Skip to main content

507. Perfect Number

easy

Decide whether a positive integer equals the sum of its proper divisors. A classic number-theory warm-up — trial division up to sqrt(n) gets you O(sqrt(n)) easily.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

A perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. A divisor of an integer x is an integer that can divide x evenly. Given an integer n, return true if n is a perfect number, otherwise return false.

Constraints

  • 1 <= num <= 10^8

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Iterating divisors d from 1 to n-1 is O(n). For n up to 10^8 that's too slow.

Hint 2

Divisors come in pairs (d, n/d). One of each pair is <= sqrt(n). So iterate d from 1 to sqrt(n).

Hint 3

For each d that divides n, add both d and n/d to the sum. Watch the special case d == n/d (perfect square) — don't double-count.

Hint 4

Subtract n at the end (the problem excludes the number itself from the divisor sum).

Solution approach

Reveal approach

Trial division up to sqrt(n). Special-case n == 1 -> return false (1 has no proper divisors). Initialize sum = 0. For d from 1 while d * d <= n: if n % d == 0, add d to sum, and if d != n / d, also add n / d. After the loop, sum holds the count of all divisors including n itself. Return sum - n == n (which is the same as sum == 2 * n). O(sqrt(n)) time, O(1) space. Cheat sheet: known perfect numbers under 10^8 are 6, 28, 496, 8128, 33550336 — for a constant-time lookup variant, hardcode those five. The trial-division version is the interview-grade answer.

Complexity

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

Related patterns

  • math
  • number-theory

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Apple

More Math practice problems

See all Math problems →