Maximum number of multiples in an array before any element | Python3 implementation of the approach ; Map to store the divisor count ; Function to generate the divisors of all the array elements ; Function to find the maximum number of multiples in an array before it ; To store the maximum divisor count ; Update ans if more number of divisors are found ; Generating all the divisors of the next element of the array ; Driver code
from math import ceil , sqrt NEW_LINE MAX = 100000 NEW_LINE divisors = [ 0 ] * MAX NEW_LINE def generateDivisors ( n ) : NEW_LINE INDENT for i in range ( 1 , ceil ( sqrt ( n ) ) + 1 ) : NEW_LINE INDENT if ( n % i == 0 ) : NEW_LINE INDENT if ( n // i == i ) : NEW_LINE INDENT divisors [ i ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT divisors [ i ] += 1 NEW_LINE divisors [ n // i ] += 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT def findMaxMultiples ( arr , n ) : NEW_LINE INDENT ans = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT ans = max ( divisors [ arr [ i ] ] , ans ) NEW_LINE generateDivisors ( arr [ i ] ) NEW_LINE DEDENT return ans NEW_LINE DEDENT arr = [ 8 , 1 , 28 , 4 , 2 , 6 , 7 ] NEW_LINE n = len ( arr ) NEW_LINE print ( findMaxMultiples ( arr , n ) ) NEW_LINE