Four Divisors - Perf Optimization

Problem is here: https://leetcode.com/problems/four-divisors/submissions/

1390. Four Divisors

Medium

Given an integer array nums, return the sum of divisors of the integers in that array that have exactly four divisors.

If there is no such integer in the array, return 0.

Example 1:

Input: nums = [21,4,7]
Output: 32
Explanation:
21 has 4 divisors: 1, 3, 7, 21
4 has 3 divisors: 1, 2, 4
7 has 2 divisors: 1, 7
The answer is the sum of divisors of 21 only.

Constraints:

• 1 <= nums.length <= 10^4
• 1 <= nums[i] <= 10^5

The code to find the Divisors of a number runs in O(n)-time. Problem is that the constraints make the overall execution time for this problem 10^4 * 10^5 = 10^9, which is intractable. Hence, even with some caching for repeated numbers, the solution timed out.
Turns out that the key to optimize this problem is to understand that the number of divisors function is a monotonic function, hence the moment that you cross 4 divisors, you can just abort the calculation. This highlighted code did the trick. Cheers, ACC.

public class Solution
{
    public int SumFourDivisors(int[] nums)
    {
        int retVal = 0;
        Hashtable cache = new Hashtable();

        foreach (int n in nums)
        {
            int sumDivisors = 0;
            if (NumberDivisors(n, cache, ref sumDivisors) == 4)
            {
                retVal += sumDivisors;
            }
        }

        return retVal;
    }

    private int NumberDivisors(int n, Hashtable cache, ref int sumDivisors)
    {
        if (cache.ContainsKey(n))
        {
            CacheItem ci = (CacheItem)cache[n];
            sumDivisors = ci.sumDivisors;
            return ci.numberDivisors;
        }

        int numberDivisors = 0;
        sumDivisors = 0;

        for (int d = 1; d <= n; d++)
        {
            if (n % d == 0)
            {
                numberDivisors++;
                sumDivisors += d;

                //Perf optmization!
                if (numberDivisors > 4)
                {
                    return numberDivisors;
                }
            }
        }

        if (!cache.ContainsKey(n))
        {
            CacheItem ci = new CacheItem(numberDivisors, sumDivisors);
            cache.Add(n, ci);
        }

        return numberDivisors;
    }
}

public class CacheItem
{
    public int numberDivisors = 0;
    public int sumDivisors = 0;

    public CacheItem(int numberDivisors, int sumDivisors)
    {
        this.numberDivisors = numberDivisors;
        this.sumDivisors = sumDivisors;
    }
}