Perfect number Java solution but facing time out for long number like "999,999,991" .....


  • 1
    A

    This is simple solution for Perfect number but I am facing timeout for number like "999,999,991". Anyone can explain how to reduce time complexity from O(n) ??

    public class Solution {
        public boolean checkPerfectNumber(int num) {
            //ArrayList<Integer> divisor = new ArrayList<Integer>();
            int sum=0;
            boolean flag = true;
            for(int i=1;i<num;i++){
                if(num%i == 0){
                    sum = sum + i;
                    if(sum > num){
                     flag = false;
                     break;
                    }
                }
            }
            if(sum<num)
                flag = false;
                return flag;
        }
    }
    

  • 5
    C

    there is no need to iterate i from 1 to num, just to Math.sqrt(num),
    because divisor larger or less than Math.sqrt(num) is Corresponding.
    e.g like number 100,it's disivors are 1,2,4,5,10,20,25,50,100. the Math.sqrt(100) = 10, since divisors appear as pairs like(1,100),(2,50)
    (4,25) (5,20) ,(10,10) ,so for number 100,iterating to 10 is enough.


Log in to reply
 

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