How to Validate a Perfect Number (Integer)?

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

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) —

推荐阅读:
“小确幸”的生活需要仪式感  西双湖作文  追求–让梦想花开  盼望着在小溪旁过新年作文  不语,最是情深  梓人传原文及翻译  种树郭橐驼传原文及翻译  送董邵南游河北序原文及翻译  原道原文及翻译  陋室铭原文及翻译 
评论列表
添加评论