1390. Four Divisors

Time: O(n √n)

Space: O(1)

Intuition

Each node value becomes sum of (values of all ancestors that equal the node's value). Root gets value 0. DFS with path value sum.

Algorithm

1Wait: "lucky numbers" - different problem. For Four Divisors: find elements with exactly 4 divisors.
2For each element: count divisors up to sqrt. If exactly 4, add sum of divisors.

Common Pitfalls

•Problem 1390 is actually "Four Divisors". Count divisors efficiently in O(sqrt(n)).

1390.cs

// Approach: For each number iterate divisors up to sqrt; count exactly 4 divisors (i, n/i, 1, n); sum those.
// Time: O(n √n) Space: O(1)

public class Solution
{
    public int SumFourDivisors(int[] nums)
    {
        int ans = 0;

        foreach (int num in nums)
        {
            int divisor = 0;
            for (int i = 2; i * i <= num; ++i)
            {
                if (num % i == 0)
                {
                    if (divisor == 0)
                        divisor = i;
                    else
                    {
                        divisor = 0;
                        break;
                    }
                }
            }
            
            if (divisor > 0 && divisor * divisor < num)
                ans += 1 + num + divisor + num / divisor;
        }

        return ans;
    }
}

Was this solution helpful?