Sum of M maximum distinct digit sum from 1 to N that are factors of K | Python 3 implementation to find the sum of maximum distinct digit sum of at most M numbers from 1 to N that are factors of K ; Function to find the factors of K in N ; Initialise a vector ; Find out the factors of K less than N ; Find the digit sum of each factor ; Sum of digits for each element in vector ; Find the largest M distinct digit sum from the digitSum vector ; Find the sum of last M numbers . ; Find the at most M numbers from N natural numbers whose digit sum is distinct and those M numbers are factors of K ; Find out the factors of K less than N ; Sum of digits for each element in vector ; Sorting the digitSum vector ; Removing the duplicate elements ; Finding the sum and returning it ; Driver Code ; Function Call
import math NEW_LINE def findFactors ( n , k ) : NEW_LINE INDENT factors = [ ] NEW_LINE sqt = ( int ) ( math . sqrt ( k ) ) NEW_LINE for i in range ( 1 , sqt ) : NEW_LINE INDENT if ( k % i == 0 ) : NEW_LINE INDENT if ( k // i == i and i <= n ) : NEW_LINE INDENT factors . append ( i ) NEW_LINE DEDENT else : NEW_LINE INDENT if ( i <= n ) : NEW_LINE INDENT factors . append ( i ) NEW_LINE DEDENT if ( k // i <= n ) : NEW_LINE INDENT factors . append ( k // i ) NEW_LINE DEDENT DEDENT DEDENT DEDENT return factors NEW_LINE DEDENT def findDigitSum ( a ) : NEW_LINE INDENT for i in range ( len ( a ) ) : NEW_LINE INDENT c = 0 NEW_LINE while ( a [ i ] > 0 ) : NEW_LINE INDENT c += a [ i ] % 10 NEW_LINE a [ i ] = a [ i ] // 10 NEW_LINE DEDENT a [ i ] = c NEW_LINE DEDENT return a NEW_LINE DEDENT def findMMaxDistinctDigitSum ( distinctDigitSum , m ) : NEW_LINE INDENT sum = 0 NEW_LINE i = len ( distinctDigitSum ) - 1 NEW_LINE while ( i >= 0 and m > 0 ) : NEW_LINE INDENT sum += distinctDigitSum [ i ] NEW_LINE i -= 1 NEW_LINE m -= 1 NEW_LINE DEDENT return sum NEW_LINE DEDENT def findDistinctMnumbers ( n , k , m ) : NEW_LINE INDENT factors = findFactors ( n , k ) NEW_LINE digitSum = findDigitSum ( factors ) NEW_LINE digitSum . sort ( ) NEW_LINE ip = list ( set ( digitSum ) ) NEW_LINE return findMMaxDistinctDigitSum ( ip , m ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 100 NEW_LINE k = 80 NEW_LINE m = 4 NEW_LINE print ( findDistinctMnumbers ( n , k , m ) ) NEW_LINE DEDENT