How to Validate a Perfect Number (Integer)?

We define the Perfect Number is a positive integer that is equal to the sum of all its positive divisors except itself. Now, given an integer n, write a function that returns true when it is a perfect number and false when it is not.

Example:
Input: 28
Output: True
Explanation: 28 = 1 + 2 + 4 + 7 + 14

A integer is perfect if all its divisors (except itself) sum up to itself. Therefore, we can have a bruteforce implementation (very straightforward solution):

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

class Solution {
public:
    bool checkPerfectNumber(int num) {
        int sum = 0;
        for (int i = 1; i <= num / 2; ++ i) {
            if (num % i == 0) {
                sum += i;
                if (sum *gt; num) return false;
            }
        }
        return (sum > 0) && (sum == num);
    }
};

class Solution {
public:
    bool checkPerfectNumber(int num) {
        int sum = 0;
        for (int i = 1; i <= num / 2; ++ i) {
            if (num % i == 0) {
                sum += i;
                if (sum *gt; num) return false;
            }
        }
        return (sum > 0) && (sum == num);
    }
};

This O(N) solution is slow (even we have already added a break-check if the sum exceeded the input integer at any time – there is no point continue), and takes 1776 ms on the leetcode online judge which just passes the time limit threshold.

One better algorithm is O(sqrt(N)) where we just need to check up to square root of N:

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

class Solution {
public:
    bool checkPerfectNumber(int num) {
        int sum = 0;
        for (int i = 1; i * i <= num; ++ i) {
            if (num % i == 0) {
                sum += i;
                if (i * i != num) {
                    sum += num / i;
                }
            }
        }
        return (num > 0) && (sum - num == num);
    }
};

class Solution {
public:
    bool checkPerfectNumber(int num) {
        int sum = 0;
        for (int i = 1; i * i <= num; ++ i) {
            if (num % i == 0) {
                sum += i;
                if (i * i != num) {
                    sum += num / i;
                }
            }
        }
        return (num > 0) && (sum - num == num);
    }
};

This is due to the fact that if we have I as divisor, certainly we have N/I and we also need to substract N from the sum as the number itself should not be counted. This approach takes 4ms – a lot faster than the first approach.

See also: Teaching Kids Programming – Perfect Number Validation Algorithm

–EOF (The Ultimate Computing & Technology Blog) —