Perfect Number

easy math

Problem

A perfect number is a positive integer that equals the sum of its positive proper divisors (excluding itself). Return true if num is a perfect number.

Inputnum = 28

Outputtrue

1 + 2 + 4 + 7 + 14 = 28.

num

def check_perfect_number(num):
    if num <= 1:
        return False
    total = 1
    d = 2
    while d * d <= num:
        if num % d == 0:
            total += d
            if d != num // d:
                total += num // d
        d += 1
    return total == num

function checkPerfectNumber(num) {
  if (num <= 1) return false;
  let total = 1;
  for (let d = 2; d * d <= num; d++) {
    if (num % d === 0) {
      total += d;
      if (d !== num / d) total += num / d;
    }
  }
  return total === num;
}

class Solution {
    public boolean checkPerfectNumber(int num) {
        if (num <= 1) return false;
        int total = 1;
        for (int d = 2; d * d <= num; d++) {
            if (num % d == 0) {
                total += d;
                if (d != num / d) total += num / d;
            }
        }
        return total == num;
    }
}

bool checkPerfectNumber(int num) {
    if (num <= 1) return false;
    int total = 1;
    for (int d = 2; d * d <= num; d++) {
        if (num % d == 0) {
            total += d;
            if (d != num / d) total += num / d;
        }
    }
    return total == num;
}

Explanation

A perfect number equals the sum of its proper divisors (all divisors except itself). The clever speed-up is to only test divisors up to √num and grab their partners for free.

Divisors come in pairs: if d divides num, then so does num / d. So instead of checking every value up to num, we loop d only while d * d <= num and add both d and num / d to the running total whenever d divides evenly.

We start total = 1 because 1 is always a proper divisor of any num > 1 (and the loop begins at d = 2). We also guard against double-counting: when d equals num / d (a perfect square root), we add it only once. At the end we return whether total == num.

Example: num = 28. The pairs found are (2, 14) and (4, 7), plus the initial 1: 1 + 2 + 14 + 4 + 7 = 28, which equals num, so the answer is true.

Because we stop at the square root, the loop runs about √num times using constant space.

Time: O(√n) Space: O(1)