DDSA Solutions

1390. Four Divisors

UnknownView on LeetCode
Math
Time: O(n √n)
Space: O(1)

Problem Overview

Each node value becomes sum of (values of all ancestors that equal the node's value).

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

  1. 1Wait: "lucky numbers" - different problem. For Four Divisors: find elements with exactly 4 divisors.
  2. 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
C#
// 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?

Related Problems