6
\$\begingroup\$

I recently encountered the Four Divisors problem on LeetCode and managed to achieve a 100% beat rate with my solution. I'd like to share it with you all and gather feedback on its effectiveness and potential optimizations.

Brief description of the problem:

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.

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.

Here's the Python code I used:

class Solution:

    def sumFourDivisors(self, nums: List[int]) -> int:
        total_sum = 0

        # Function to calculate the sum of divisors for a given number
        def sumFourDivisors_aux(n):
            divisors_sum = 1 + n  # Start with 1 and n itself

            # If n is a perfect square, it cannot have exactly 4 divisors
            if (n**0.5).is_integer():
                return 0

            # If n is divisible by 4 and not equal to 8, it cannot have exactly 4 divisors
            if n % 4 == 0 and n != 8:
                return 0

            # Check if n is divisible by 2 (except 2 itself) and update divisors accordingly
            if n % 2 == 0 and n != 2:
                divisors_sum += 2 + n // 2

            # Check only the odd divisors from 3 up to square root of n
            for d in range(3, int(n**0.5) + 1, 2):
                if n % d == 0:
                    if divisors_sum != 1 + n:  # If divisors are already more than 2, return 0
                        return 0
                    divisors_sum += d + n // d  # Add divisor and its pair
            return divisors_sum

        # Iterate through the numbers in the input list
        for num in nums:
            divisor_sum = sumFourDivisors_aux(num)
            if divisor_sum > 1 + num:  # If the sum of divisors is greater than num + 1
                total_sum += divisor_sum  # Add it to the total sum
        return total_sum


The problem is indeed simple. However, I noticed certain conditions that could reduce the number of operations from the standard solution for this problem. By checking if n % 4 == 0 and n != 8: and immediately after, if n % 2 == 0 and n != 2:, we ensure that the number with four divisors is either 8 or in the form 2pi or pi . pj, where pi and pj are different odd primes.

Therefore, we only need to check the odd divisors in the for loop:
for d in range(3, int(n**0.5) + 1, 2):,
which differs from the straight forward solution using:
for d in range(2, int(n**0.5) + 1, 1):.

I'd appreciate any feedback or suggestions for further optimization. Thank you!

\$\endgroup\$
0

4 Answers 4

5
\$\begingroup\$

nested function

Thank you for breaking out a Helper.

    def sumFourDivisors(...
        ...
        def sumFourDivisors_aux(n):

I will offer my usual advice: Make this a separate function. That way it will be available at {class, module} level to your test suite. BTW good job on avoiding shadowing and coupling, via the only slightly awkward approach of using both n and num identifiers.

Also, please offer us a docstring:

    def sumFourDivisors_aux(n: int) -> int:
        """Calculates the sum of divisors for a given number."""

cache decorator

The input list can mention same integer multiple times. Use a @lru_cache to avoid re-doing the work.

signature

        def sumFourDivisors_aux(n):
            divisors_sum = 1 + n ...
        ...
        divisor_sum = sumFourDivisors_aux(num)
        if divisor_sum > 1 + num:

The caller needs to know too much about what's happening in the helper. Maybe returning a single integer is inconvenient, and we'd be better off returning a (num_divisors, sum) tuple.

        if divisors_sum != 1 + n:  # If divisors are already more than 2, ...
            return 0

That test on the inside of the helper might more conveniently be examining "number of divisors".

Or maybe you'd find that storing a set of all found divisors is most convenient.

ULP

One way to test for "perfect square" would be to call math.isqrt(), and see if squaring the result gives you your original number back. Recall that a python int can be very big, bigger than will fit in a FP 53-bit significand.

It wasn't immediately obvious to me that this test would always work:

            if (n**0.5).is_integer():

But then I saw the "bounded by 1e5" constraint, and found that line a little more convincing.

You might possibly wish to hang onto that square root, for subsequent use as a range() argument.

special cases

    # If n is divisible by 4 and not equal to 8, it cannot have exactly 4 divisors

This and the sqrt() check are true, but absent any timing code it's not obvious that they are worth the effort. We could e.g. ask whether divisible by other squares such as 9, with diminishing returns.

For that matter, it's not obvious if checking for "even" and passing step=2 into range() is worth it. Initializing with 1 + n is a special case; we don't initialize with 0 due to that step=2 parameter.

early exit

The for d loop commits to looping up to the root, which in the contest will often be around 316. We might uncover half a dozen divisors and still have lots more to try. It seems natural to bail out early after discovering 4 divisors. [It has an early return clause, but it wasn't immediately obvious to me how likely it is to trigger.]

numba

The current code is a fair candidate for JITting. It's often enough that a time-consuming helper turns out to run just 2X faster or some similarly disappointing JIT speedup. But here the integer operations and low number of function calls suggests a good fit.

As long as we're contemplating runtime support that won't be available under contest conditions, consider turning the input list into a numpy array. Then we can broadcast 316 trial divisions across the array, running at Fortran / C++ speed.

primes

Consider adopting a quite different approach to the problem, with sieve or wheel. Initialize by obtaining all primes up to 316. Then use that ten thousand times to compute what the contest requires.

\$\endgroup\$
3
  • \$\begingroup\$ The for d loop does return early if it finds more than 4 divisors, doesn't it? It's a little tricky to see because it works on the sum so far rather than simply counting. \$\endgroup\$ Commented Apr 20 at 15:32
  • \$\begingroup\$ @TobySpeight, it's a good observation, thank you. I guess I'm saying that from just looking at the for + if ... return, it's not obvious to me what the time complexity of that loop is. Even if code is correct, we still might want an edit prior to merging PR if the code is tricky and will cause maintenance headaches. Optional debug instrumentation like counters, and a test suite, could go a long way toward making the OP code more transparently obvious. \$\endgroup\$
    – J_H
    Commented Apr 20 at 15:41
  • \$\begingroup\$ Oh, definitely. I completely agree with you here. It's a shame that the unit tests and benchmarks are missing, because we can see how to construct difficult cases. And challenge setters will certainly aim to stress the solutions. \$\endgroup\$ Commented Apr 20 at 15:46
4
\$\begingroup\$

We could move the test for divisibility by 4 before the more expensive square-root operation.

Note also that we have a specific code path for number 8, so we could hard-code a return there:

            # If n is divisible by 4 and not equal to 8, it cannot have exactly 4 divisors
            if n % 4 == 0:
                return 15 if n == 8 else 0

Instead of checking divisibility by all odd divisors up to √n, consider using a prime number generator to consider only prime divisors.

It may be more efficient to perform a (possibly partial) prime factorisation. "Possibly partial" because we can abort the factorisation as soon as we discover that we have neither a product of two primes nor an exact cube of a prime (these are the only numbers with exactly 4 factors). Note that these conditions automatically account for most of our special cases without extra work - only the perfect-square test then still has value (and I would have liked to see evidence that proves it outweighs its cost).

I would probably change the internal function to always return 0 for prime inputs, so we can loop like a native:

    return sum(map(sumFourDivisors_aux, nums))
\$\endgroup\$
4
\$\begingroup\$

I found it odd (pardon the pun) that your “divisible by 4” check is before your “divisible by 2” check. You only need to check if the number is divisible by 4 if it is divisible by 2, which is already a special case you’re checking for.

Your “divisible by 4 and not equal to 8” test is far too specific. It can be extended to additional factors. When you find a value for d where n % d == 0, you could check if n % d**2 == 0 and n == d ** 3, and short circuit the values \$3^3, 5^3, 7^3, 11^3, …, 43^3\$ too.

However, a much better speed up will come from reducing the search space of your trial division. After you discover a d where n % d == 0, you are continuing to look for another divisor up to \$\sqrt n\$, where as you could stop at \$\sqrt{n/d}\$.

Consider n = 97667. You take the square root, and start searching for possible divisors up to 312, and eventually find the divisor 101, and the “corresponding divisor” of 97667 // 101, which is 967. At this point, you continue searching for other divisors, with 103, 105, 107, and so on, but the only other possible divisors of 97667 would have to come from factors of 967. Your trial divisors have already exceeded the square-root of that, so we can immediately conclude 967 must be prime and stop.

In the case of n = 77531, you would search for divisors up to 278. The first divisor you’d find is 31, with the corresponding divisor of 77531 // 31, which is 2501. Since \$31^2 \lt 2501\$, you’d have to continue searching for trial divisors, testing 33, 35, 37, up to 49 … but you would find 41 is another divisor, so 77531 would have more than 4 divisors.

As mentioned by others, for a long list of nums, you’d do better by constructing (via a sieve) a list of primes up to isqrt(max(nums)). Or since the upper limit is given as 1e5, simply embed the first 65 prime numbers in your program.

\$\endgroup\$
-1
\$\begingroup\$

Here is an updated version of the code:

class Solution:
    # a set of prime numbers that are less than sqrt(10^5)
    PRIMES = [2 ,3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317]
    
    def sum_of_four_divisors(self, n):
        
        sqrt = n**0.5          
        sum_of_divisors = 1 + n # Note that 1 and n are always divisors
        divisor_sum = sum_of_divisors
        
                        
        '''
        Main concept around the iteration:
            if n has exactly 4 divisors, then n = p*q, where p and q are different prime numbers
            or n = p^3, where p is a prime number.
        '''
                

        for prime in Solution.PRIMES:
            if prime > sqrt: # Stop the loop if the prime number is greater than the square root of n
                break
            if n % prime**2 == 0: 
                # if n is divisible by a prime number squared and it is the cube of the prime number
                # then the number have 4 divisors and it sum is (1+prime+prime^2+prime^3) = (1+prime)*(1+prime^2)
                # otherwise return 0 (the number has an odd number of divisors)
                return (prime**2+1)*(1+prime) if n == prime**3 else 0
            if n!= prime and n % prime == 0:
                # if n is not the current prime number and n is divisible by the prime number
                # then add the prime number and the result of the division of n by the prime number
                # to the sum of divisors, also check if the sum of divisors were already updated and return 0 leaving the loop early
                if divisor_sum != sum_of_divisors:
                    return 0
                divisor_sum += prime + n//prime


        if div == sum_of_divisors:  # if the number is prime return 0
            return 0


        return divisor_sum

    def sumFourDivisors(self, nums):
        return sum(map(self.sum_of_four_divisors, nums))

Main changes:

  • Added a set of primes up to 316 (sqrt(10^5))
  • Removed the perfect square check
  • Interation for the primes up to sqrt(n)
  • Added conditions in the for loop that were implemented only to the number 2 on the first version of the code
  • Added def sumFourDivisors(self, nums): return sum(map(self.sum_of_four_divisors, nums)) as proposed by Toby Speight
\$\endgroup\$
2
  • \$\begingroup\$ You may wish to post your “answer” as a new question. Then we can critique it, giving feedback on areas that still need improvement. Just post a link in the new question back to this one, and add a link in this one to the new question. \$\endgroup\$
    – AJNeufeld
    Commented Apr 21 at 0:02
  • 1
    \$\begingroup\$ Actually, don’t post it as a new question for review until you’ve fixed the new bug. \$\endgroup\$
    – AJNeufeld
    Commented Apr 21 at 0:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.