Simple Java Solution


  • 22
    public class Solution {
        public boolean checkPerfectNumber(int num) {
            if (num == 1) return false;
            
            int sum = 0;
            for (int i = 2; i <= Math.sqrt(num); i++) {
                if (num % i == 0) {
                    sum += i;
                    if (i != num / i) sum += num / i;
                }
            }
            sum++;
            
            return sum == num;
        }
    }
    

    Update Enlightened by discussion below by @StefanPochmann and @jdrogin, in the given range we don't need to test if (i != num / i) before add num / i to sum.

    public class Solution {
        public boolean checkPerfectNumber(int num) {
            if (num == 1) return false;
            
            int sum = 0;
            for (int i = 2; i <= Math.sqrt(num); i++) {
                if (num % i == 0) {
                    sum += i + num / i;
                }
            }
            sum++;
            
            return sum == num;
        }
    }
    

  • 5
    C

    just return sum == num


  • 4

    same concept but you can avoid the Sqrt(num) calculation by checking square instead. Also, that inner if statement can be avoided.

        public bool CheckPerfectNumber(int num) {
            if (num < 2) return false;
            int sum = 1;
            for (int x = 2; x * x <= num; x++)
            {
                if (num % x == 0)
                {
                    sum += x;
                    sum += num / x;
                }
            }
            
            return sum == num;
        }
    

  • 0
    B

    My solution pretty much the same:

    public boolean checkPerfectNumber(int num) {
        
        if (num <= 1)
            return false;
        
        int sq = (int)Math.sqrt(num);
        
        int sum = 0;
        
        for (int i = 1; i <= sq; i ++){
            
            if  (num%i == 0){
                sum+=i;
                int j = num / i;
                if (i != 1)
                    sum+=j;
            }    
            
        }
        return (sum == num);    
    }
    

    It was accepted. Then I checked your solution found one line I missed.

    if (i != num / i) sum += num / i;

    So either test cases are not good OR a square numbers are NOT perfect number. The latter is true according to this link:

    http://math.stackexchange.com/questions/1701915/could-a-square-be-a-perfect-number/1702054


  • 1

    @jdrogin said in Simple Java Solution:

    that inner if statement can be avoided

    Can you prove that?


  • 3

    @StefanPochmann good catch, I have no proof, in fact I don't even know why I was thinking that in the first place. I suppose because I missed that when I solved the problem and it passed the test cases, I didn't even really think what it was for. HOWEVER, it does turn out to be true at least for the range input for this problem

    Note: The input number n will not exceed 100,000,000. (1e8)
    
    if (i != num / i) sum += num / i;
    

    this case is guarding against the square root being adding twice which will only occur for inputs which are perfect squares (4, 9, 16, 25, 36, 49, etc.). I wrote a script to check if any squares were effected by my "mistake" code either by turning a true to false or vice versa and none were. Does that count as a proof? LOL!


  • 0

    @jdrogin I'd say it does count as proof for the given problem's range. Seeing your test code might be better, but your description convinced me that you did it right. Also, I had already done it myself :-). I even checked squares up to 30000002 or so. @bellevue also already showed that there can't be false negatives (perfect numbers judged non-perfect) but I'm still wondering about false positives (non-perfect numbers judged perfect). In general, I mean, not in the given problem's small range.


  • 2

    Since there are only a few examples, it can be exhaustively compared via a switch:

    boolean checkPerfectNumber(int num) {
      switch(num) {
        case 6: case 28: case 496: case 8_128: case 33_550_336: return true;
        default: return false;
      }
    }
    

    https://discuss.leetcode.com/topic/85534/2-simple-java-solutions-via-stream-and-a-contant-time


  • 0
    Y

    Not sure if I'm getting right, correct me if I'm wrong.
    But if you include "<=sqrt(num)", and also do sum += i + num / i;:
    Some number like 100 will add 10 for 2 times right? It won't interfere the final result since no perfect number will have this issue, but is this where it has a flaw?


  • 0
    J

    @shawngao It is highly possible that sum > num for the first several loops. Program could return early if you add such condition.


  • 0
    X

    @Yibing_Shi I am thinking about this part, maybe a perfect number don't have this issue, it is a flaw but we can also add more details in loop to judge if i*i == num, if this no more num/i added. :)


  • 0
    2

    @shawngao just use int sum =1, not sum++;
    because for (int i = 2; i <= Math.sqrt(num); i++)
    i =1 is already sloved by int sum =1;


  • 0
    Y

    You can use 'while' to avoid including 'Math' here.

    class Solution {
        public boolean checkPerfectNumber(int num) {
            if(num == 1 ) return false;
            int sum = 0;
            int i = 2;
            while(num / i > i) {
                if(num % i == 0) {
                    sum += i + num / i;
                }
                i ++;
            }
            return sum + 1 == num;
        }
    }
    

  • 0
    S

    I can prove it, @jdrogin, @StefanPochmann, by proving that an integer who is the square of another integer is not a perfect number.

    If an integer X is square of another integer N:
    X = N^2 = 1 + 3 + 5 + 7 + ... + (2N-1)

    If X is a perfect number, since 2N-1 is the biggest factor, and 3 is the smallest (other than 1), then
    X = N^2 = 3(2N-1)
    N^2 - 6N + 3 = 0
    There is no real integer solution for this equation (closest N=5 or 6).

    So, any integer that's a square of another integer will not be a perfect number. Hence, in the above solution, adding the 2nd sqrt to the sum would not matter as it falls short anyway. For examples,
    9 = 1 + 3 + 5 > 1 + 3 + 3
    16 = 1 + 3 + 5 + 7 > 1 + 2 + 4 + 4


  • 0

    @superdude1688 Huh? Your 2N-1 and 3 aren't factors but addends. And what about all the others?


Log in to reply
 

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