Problem Statement

You are given an integer n. You need to check if the number is a perfect number or not. Return true if it is a perfect number, otherwise, return false.

A perfect number is a positive integer that is equal to the sum of its proper divisors, excluding the number itself. For example, 6 is a perfect number because its divisors are 1, 2, and 3, and 1 + 2 + 3 = 6.

Examples

Example 1:

Input: n = 6
Output: true

Explanation: Proper divisors of 6 are 1, 2, 3.
So, 1 + 2 + 3 = 6

Example 2:

Input: n = 9
Output: false

Explanation: Proper divisors of 9 are 1, 3.
So, adding them 1 + 3 = 4.

Approaches

1️⃣ Brute Force Approach

Intuition:

Given a number, all its proper divisors (divisors that divide the number without leaving any remainder, excluding the number itself) can be found and summed up. Then, the sum can be compared with the number itself. If the sum is the same as the number, then it is a perfect number, otherwise, it is not.

Approach:

1. Initialize a variable with 0 to store the sum of the proper divisors.
2. Start iterating from 1 to the given number(excluding) using a loop variable, and check whether the number is divisible completely (leaving the remainder zero) by the loop variable.
3. If it is divisible completely, the current value of the loop variable is a proper divisor which is added to the sum storing sum of proper divisors.
4. After the sum is calculated, compare it with the given number. If found equal, the given number is perfect, otherwise, it is not.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to find whether the
    number is perfect or not */
    bool isPerfect(int n) {
        
        /* Variable to store the sum
        of all proper divisors */
        int sum = 0;
        
        // Loop from 1 to n
        for(int i=1; i < n; ++i) {
            
            // Check if i is a proper divisor
            if(n % i == 0){
                // Update sum
                sum = sum + i;
            }
        }
        
        // Compare sum and n
        if(sum == n) return true;
        return false;
    }
};

int main() {
    int n = 6;
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to find whether the
     given number is perfect or not */
    bool ans = sol.isPerfect(n);
    
    if(ans) {
        cout << n << " is a perfect number." << endl;
    } else {
        cout << n << " is not a perfect number." << endl;
    }
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(N) – Running a loop from 1 to N.
• Space Complexity:O(1) – Using a couple of variables i.e., constant space, regardless of the size of input.

2️⃣ Square Root (Optimal)

Intuition:

The previous approach can be optimized by using the property that for any non-negative integer n, if d is a divisor of n then n/d is also a divisor (counterpart divisor) of n. This property is symmetric about the square root of n. By traversing just the first half, the redundant iterations and computations can be avoided improving the efficiency of the algorithm.

Approach:

1. Initialize a variable with 0 to store the sum of the proper divisors.
2. Start iterating from 1 to square root of the given number using a loop variable, and check whether the number is divisible completely (leaving the remainder zero) by the loop variable.
3. If it is divisible completely, the current value of the loop variable is a proper divisor which is added to the sum storing sum of proper divisors. Also, using the property discussed above, another proper divisor can be found.
4. Note: Before adding the counterpart divisor, it should be checked if both the proper divisors are different and the counterpart divisor is not the number itself. If they are different and the counterpart divisor is not the number itself, the counterpart divisor should be added to the sum. Otherwise, the counterpart divisor should not be added to the sum ensuring that the divisor is not added twice.
5. After the sum is calculated, compare it with the given number. If found equal, the given number is perfect, otherwise, it is not.

Edge Case:

• When the given number is 1, there are no proper divisors of 1, i.e., the sum of proper divisors of the number is 0. Hence, 1 is not a perfect number.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to find whether the
    number is perfect or not */
    bool isPerfect(int n) {
        // Edge case
        if(n == 1) return false;
        
        /* Variable to store the sum
        of all proper divisors */
        int sum = 0;
        
        // Loop from 1 to square root of n
        for(int i=1; i <= sqrt(n); ++i) {
            
            // Check if i is a proper divisor
            if(n % i == 0){
                // Update sum
                sum = sum + i;
                
                /* Add the counterpart divisor
                if it's different from i and
                if it is not n itself */
                if(n/i != n && i != n/i) {
                    sum = sum + (n/i);
                }
            }
        }
        
        // Compare sum and n
        if(sum == n) return true;
        return false;
    }
};

int main() {
    int n = 6;
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to find whether the
     given number is perfect or not */
    bool ans = sol.isPerfect(n);
    
    if(ans) {
        cout << n << " is a perfect number." << endl;
    } else {
        cout << n << " is not a perfect number." << endl;
    }
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(sqrt(N)) – Running a loop from 1 to square root of N.
• Space Complexity:O(1) – Using a couple of variables i.e., constant space, regardless of the size of input.