C++ 6 lines 'normal' solution ( 3 lines actually...)


  • 2
        bool checkPerfectNumber(int num) {
            vector<int>res(1,1);
            int upper=num;
            for(int i=2;i<upper;i++) if(num%i==0) res.push_back(i), res.push_back(num/i), upper=num/i;
            int sum=0;
            for(auto i:res) sum+=i;
            return sum==num && num!=1;
        }
    

    Update(8/6/2017): I just found I don't need to keep updating upper if I know where it will land (when i == num/i, it doesn't matter if i< or <= sqrt(num) as explained in comment), and it reduces run time from 1055ms to 3ms, well...

        bool checkPerfectNumber(int num) {
            vector<int>res(1,1);
            for(int i=2;i<sqrt(num);i++) if(num%i==0) res.push_back(i), res.push_back(num/i);
            int sum=0;
            for(auto i:res) sum+=i;
            return sum==num && num!=1;
        }
    

    Update: Why would I need a vector?

        bool checkPerfectNumber(int num) {
            int sum=1;
            for(int i=2;i<sqrt(num);i++) if(num%i==0) sum += i + num/i;
            return sum==num && num!=1;
        }
    

    Thanks @MAPLELEAF2012 for advice.
    The comprehensive version if we take the perfect square into account, in which case sum(49) is 1+7=8, not 1+7+7=15 or 1.

        bool checkPerfectNumber(int num) {
            int sum=1;
            for(int i=2;i<=sqrt(num);i++) if(num%i==0) sum += i + (i==num/i ? 0 : num/i);
            return sum==num && num!=1;
        }
    

  • 0
    M

    Nice idea of updating the for loop index upper bound. Do we need to check whether i == num / i or not before we push num / i into res also? (e.g. when num is 49, sum shall be 8, instead of 15)


  • 0

    @MapleLeaf2012 Thanks for pointing out, i didn't notice that before. Emm... so I looked into it, and I found it only affects the perfect squares, i.e. 4, 9, 16..., etc. And according to wikipedia, all the perfect numbers within the input range of problem description(0 ~ 100,000,000. (1e8)) are not perfect sqaures, actually there are only 5 numbers {6, 28, 496, 8128, 33550336}, (that's why i put 'normal' solution in the title), so i guess it explains that we don't need to check whether i == num / i only for solving this problem.
    But it's just a single line and I think in the aspect of accuration, it would be better to have that in the code.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.