How to Validate a Perfect Number (Integer)?

  • 时间:2020-10-05 13:36:40
  • 分类:网络文摘
  • 阅读:87 次

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.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
网站站长赚钱的七条经验分享  一道求比例尺的问题  欧拉的故事  分羊的故事  千里马的故事  监狱里的数学研究  比和比例的历史  平均数、中位数和众数的区别  黄金分割的历史  蝴蝶效应 
评论列表
添加评论