Teaching Kids Programming – Perfect Number Validation Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

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 = 6
Output: true

Example 3:
Input: num = 496
Output: true

Example 4:
Input: num = 8128
Output: true

Example 5:
Input: num = 2
Output: false

Algorithm to Validate a Perfect Number

We go through each number between 1 to N//2 inclusive, then add the sum if it is one of the divisor. The time complexity is O(N). We can fail and exit once the current sum is more than the origin number.

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        if num <= 0:
            return False
        s = 0
        for i in range(1, num//2+1):
            if num % i == 0:
                s += i
                if s > num:
                    return False
        return s == num

class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        if num <= 0:
            return False
        s = 0
        for i in range(1, num//2+1):
            if num % i == 0:
                s += i
                if s > num:
                    return False
        return s == num

We actually only need to check from 1 to Sqrt(N), as if we have a divisor a, we must have another N/a unless a*a==N (special case).

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        if num <= 0:
            return False
        i, s = 1, 0
        while i * i <= num:
            if num % i == 0:
                s += i
                if i * i != num:
                    s += num // i                    
            i += 1
        return s == num + num

class Solution:
    def checkPerfectNumber(self, num: int) -> bool:
        if num <= 0:
            return False
        i, s = 1, 0
        while i * i <= num:
            if num % i == 0:
                s += i
                if i * i != num:
                    s += num // i                    
            i += 1
        return s == num + num

One special to notice is that we consider 1 to be a factor and thus num is another so that we need to deduct num from the sum. The time complexity is O(Sqrt(N)).

See also: How to Validate a Perfect Number (Integer)?

–EOF (The Ultimate Computing & Technology Blog) —