1390.Four Divisors

In [67]:

from math import sqrt
from typing import List
import random, sys
sys.path.append("/home/swyoo/algorithm/")
from utils.verbose import logging_time

1390. Four Divisors

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.

Navie

Idea

Find all distinct divisors.
Enumerate all possible numbers to be divisable.

Let $n$ be the maximum value of elements in nums
Let $m$ be the size of nums.

It takes $O(mn)$

This algorithm is too slow to pass the efficiency test for the leetcode problem.

we can improve findDivs(x) function, which helps to find all divisors of x

In [27]:

class Solution1:
    @logging_time
    def sumFourDivisors(self, nums: List[int]) -> int:
        """ TLE, too slows. """
        findDivs = lambda x: [i for i in range(1, x + 1) if x % i == 0]
        ans = 0
        for e in nums:
            Divs = findDivs(e)
            if len(Divs) == 4:
                ans += sum(Divs)
        return ans

sol1 = Solution1()

In [28]:

nums = [21,4,7]
print(sol1.sumFourDivisors(nums, verbose=True))

WorkingTime[sumFourDivisors]: 0.02003 ms
32

Improved Version

Notice that divisible numbers can be found pairwisely.
e.g., $n = 100$, (1,100), (2,50), (4,25), (5,20), (10,10) can be found.

$2^k = n$, $k=\sqrt n$.
Therefore, the time complexity can be improved as follows. $O(m\sqrt n)$

In [31]:

class Solution2:
    @logging_time
    def sumFourDivisors(self, nums: List[int]) -> int:
        """ improved """
        def findDivs(x):
            res = []
            for i in range(1, int(sqrt(x)) + 1):
                if x % i == 0:
                    if x / i == i:
                        res.append(i)
                    else:
                        res.extend([i, int(x / i)])
            return res
        ans = 0
        for e in nums:
            Divs = findDivs(e)
            if len(Divs) == 4:
                ans += sum(Divs)
        return ans

sol2 = Solution2()

In [32]:

size = 1000
A = [random.randint(0, 100* size) for i in range(size)]
print(sol1.sumFourDivisors(A, verbose=True))
print(sol2.sumFourDivisors(A, verbose=True))

WorkingTime[sumFourDivisors]: 2433.62427 ms
12444942
WorkingTime[sumFourDivisors]: 8.99243 ms
12444942

In [34]:

def findDivs(x):
    res = []
    for i in range(1, int(sqrt(x)) + 1):
        if x % i == 0:
            if x / i == i:
                res.append(i)
            else:
                res.extend([i, int(x / i)])
    return res

In [36]:

findDivs(100)

[1, 100, 2, 50, 4, 25, 5, 20, 10]

Referenece

[1] Find all divisors of a natural number | Set 1 geeksforgeeks

In [None]: