CODEWITHSUNDEEP
pythonpython-3.xalgorithmperformance
user14841220
user14841220

Reputation: 11

Find the item in a list with the maximum number of factors that appear in that same list and output maximum (Python)

I am trying to write a function that takes in a list of integers and finds the maximum number of factors that appear in that same list. For example, if I have a list with contents 9,5,6,3,2 then 9 has two factors that appear in the list (9 & 3), 5 has one factor that appears in the list (5), 6 has three factors that appear in the list (6, 3, 2), and so on. In this case, the output would be 3 (6 has the max number of factors that appear in the list with 3 total). This is what I have so far:

def divisibility(keys):
    #sort keys in descending order - larger numbers w same divisors
    #will always have more factors so we can remove them from the list if they are used
    sortkeys = sorted(keys,reverse=True)
    #compare max divisibility to divisibility of each number in keys 
    #(will always be at least 1 since a number is always divisible by itself)
    max_divisibility = 1
    while len(sortkeys) > 0:
        divisibility = 1
        #when done testing largest number, remove it from the list
        removekeys = [sortkeys[0]]
        for i in range(1,len(sortkeys)):
            #test largest number
            if sortkeys[0] % sortkeys[i] == 0:
                divisibility += 1
                #remove that number from the list
                removekeys.append(sortkeys[i])
        if divisibility > max_divisibility:
             max_divisibility = divisibility
        #remove keys in list
        sortkeys = list(set(sortkeys).difference(removekeys))
    return max_divisibility

This works sometimes, but in the case mentioned above it fails, because 3 is removed from the list on the first pass, so by the time we get to 6 there are only two factors of 6 left in the list (6 and 2). I know you could just check every single element of the list, but I'd really like to make this as efficient as possible, so any advice there would be appreciated.

Upvotes: 1

Views: 567

Answers (3)

Alain T.
Alain T.

Reputation: 42139

You can use sum() in a comprehension to count the factors of each number and then max() to get the highest count:

def maxFactors(N): return max(sum(a%b==0 for b in N) for a in N)

maxFactors([9,5,6,3,2]) # 3

While it may be possible to reduce the complexity from O(n^2) to O(NlogN) or less, the actual performance may not be better because of the higher overhead required.

for example (using sorting and binary search):

from bisect import bisect_right
def maxFactors(N):
    sN     = sorted(N)
    return max(sum(n%sN[i]==0 for i in range(0,bisect_right(sN,n))) for n in N)

This is actually slower than the previous one on the small example [9,5,6,3,2] but performs 3% better for a list of 50 values and 45% better on 500 values.

Some optimization could provide better performance when the data meets specific conditions such as when the ratio of maximum/minimum is smaller than the number of elements.

for example:

from collections import Counter
def maxFactors(N):
    fRange = range(1,max(N)//min(N)+1)
    cN     = Counter(N)
    return max(sum(cN[n//f] for f in fRange if n%f==0) for n in cN)

This would give an O(NxF) complexity where F is the ratio of maximum/minimum. It is also slower than the first one on the small example but runs 8 times faster on range(25,75) and 38 times faster on range(250,750)

To get the best performance you could select one of these 3 based on a quick assessment of the data. For example, use the Counter() approach when the max/min ratio is less than len(N) or use the binary search when len(N) is large enough.

def maxFactors(N):
    fRange = range(1,max(N)//min(N)+1)
    if len(fRange)<len(N):
        cN = Counter(N)
        return max(sum(cN[n//f] for f in fRange if n%f==0) for n in cN)
    if len(N) < 50:
        return max(sum(a%b==0 for b in N) for a in N)
    sN = sorted(N)
    return max(sum(n%sN[i]==0 for i in range(0,bisect_right(sN,n))) for n in sN)

Upvotes: 2

DarrylG
DarrylG

Reputation: 17166

A simpler algorithm is the following.

def factors(n, lst):
    ' Count of factors of n in list lst '
    return sum(n % i == 0 for i in lst)

def divisibility(keys):
    ' Find element in keys with most factors '
    return max(factors(k, keys) for k in keys)

lst = [9,5,6,3,2]
print(divisibility(lst))  # 3

Upvotes: 3

VirtualScooter
VirtualScooter

Reputation: 1888

I like @DarrylG's answer, but still, here's a modified version of the algo in the question, which does print 3:

def divisibility2(keys):
    #sort keys in descending order - larger numbers w same divisors
    #will always have more factors so we can remove them from the list if they are used
    sortkeys = sorted(keys)
    #compare max divisibility to divisibility of each number in keys 
    #(will always be at least 1 since a number is always divisible by itself)
    max_divisibility = 1
    while len(sortkeys) > 0:
        divisibility = 1
        #when done testing largest number, remove it from the list
        largest = sortkeys.pop()
        for elem in sortkeys:
            #test largest number
            if largest % elem == 0:
                divisibility += 1
        if divisibility > max_divisibility:
             max_divisibility = divisibility
    return max_divisibility

Upvotes: 1

Related Questions