Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/507.html

507. Perfect Number (Easy)

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

Note: The input number n will not exceed 100,000,000. (1e8)

Related Topics:
Math

Similar Questions:

Solution 1.

  • class Solution {
        public boolean checkPerfectNumber(int num) {
            if (num <= 0)
                return false;
            int[][] primeFactorization = primeFactorize(num);
            long factorsSum = 1;
            for (int[] primePower : primeFactorization) {
                int prime = primePower[0], power = primePower[1];
                long primeSum = 0;
                long factor = 1;
                for (int i = 0; i <= power; i++) {
                    primeSum += factor;
                    factor *= prime;
                }
                factorsSum *= primeSum;
            }
            return factorsSum == (long) (2 * num);
        }
    
        public int[][] primeFactorize(int num) {
            List<Integer> primes = new ArrayList<Integer>();
            List<Integer> powers = new ArrayList<Integer>();
            if (num % 2 == 0) {
                primes.add(2);
                int power2 = 0;
                while (num % 2 == 0) {
                    num /= 2;
                    power2++;
                }
                powers.add(power2);
            }
            int prime = 3;
            while (num > 1) {
                if (num % prime == 0) {
                    primes.add(prime);
                    int power = 0;
                    while (num % prime == 0) {
                        num /= prime;
                        power++;
                    }
                    powers.add(power);
                }
                prime += 2;
            }
            int length = primes.size();
            int[][] primeFactorization = new int[length][2];
            for (int i = 0; i < length; i++) {
                primeFactorization[i][0] = primes.get(i);
                primeFactorization[i][1] = powers.get(i);
            }
            return primeFactorization;
        }
    }
    
    ############
    
    class Solution {
        public boolean checkPerfectNumber(int num) {
            if (num == 1) {
                return false;
            }
            int s = 1;
            for (int i = 2; i * i <= num; ++i) {
                if (num % i == 0) {
                    s += i;
                    if (i != num / i) {
                        s += num / i;
                    }
                }
            }
            return s == num;
        }
    }
    
  • // OJ: https://leetcode.com/problems/perfect-number/
    // Time: O(sqrt(N))
    // Space: O(1)
    class Solution {
    public:
        bool checkPerfectNumber(int n) {
            if (n == 1) return false;
            int sum = 0;
            for (int i = 1; i * i <= n; ++i) {
                if (n % i) continue;
                sum += i;
                if (i != 1 && n / i != i) sum += n / i;
                if (sum > n) return false;
            }
            return sum == n;
        }
    };
    
  • class Solution:
        def checkPerfectNumber(self, num: int) -> bool:
            if num == 1:
                return False
            s, i = 1, 2
            while i * i <= num:
                if num % i == 0:
                    s += i
                    if i != num // i:
                        s += num // i
                i += 1
            return s == num
    
    ############
    
    class Solution(object):
      def checkPerfectNumber(self, num):
        """
        :type num: int
        :rtype: bool
        """
        ans = 1
        div = 2
        while div ** 2 <= num:
          if num % div == 0:
            ans += div
            ans += num / div
          div += 1
        return ans == num if num != 1 else False
    
    
  • func checkPerfectNumber(num int) bool {
    	if num == 1 {
    		return false
    	}
    	s := 1
    	for i := 2; i*i <= num; i++ {
    		if num%i == 0 {
    			s += i
    			if i != num/i {
    				s += num / i
    			}
    		}
    	}
    	return s == num
    }
    

All Problems

All Solutions