Perfect Number

Problem

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)

Solution

O(sqrt(n)) Time Solution

public class Solution {
    public boolean checkPerfectNumber(int num) {
        if (num <= 1) return false;
        int sum = 1; //sum starts from 1
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) sum += num / i == i ? i : i + num / i;
        }
        return sum == num;
    }
}

Analysis

This problem can be solved in O(n) time by brute force
However, that will get TLE in Leetcode
In the solution above, the runtime is reduced to O(sqrt(n))
This is because we add two divisors at the same time as long as it's not sqrt of num
Notice that we init sum = 1 so that we can start i from 2