1390. Four Divisors

main.md

Leetcode #1390

Approach

The approach was to find the factors of each num in the nums array, did this by iterating from 1 to sqrt(num), then used a set to store the factors (to avoid repetition in the case of perfect squares), then we check for the number with factors size of 4, and add the sum of all the 4 factors to the res value.

class Solution {
public:
    int sumFourDivisors(vector<int>& nums) {
        int res = 0;

        set<int> temp;

        for(int i = 0; i < nums.size(); i++) {
            int num = nums[i];

            for(int n = 1; n <= sqrt(num); n++) {
                if(num % n == 0){
                    temp.insert(n);
                    temp.insert(num/n);
                }

            }

            if(temp.size() == 4) {
                for(int el : temp) {
                    res += el;
                }
            }

            temp.clear();
        }
        

        return res;
    }
};

Complexities

Space complexity: O(N)

Time Complexity: O(N * sqrt(M)) - N is the size of the input, and M is the largest number in the array