Smallest integer with digit sum M and multiple of N | Python 3 implementation of the above approach ; Function to return digit sum ; Function to find out the smallest integer ; Start of the iterator ( Smallest multiple of n ) ; Driver code
from math import floor , pow NEW_LINE import sys NEW_LINE def digitSum ( n ) : NEW_LINE INDENT ans = 0 ; NEW_LINE while ( n ) : NEW_LINE INDENT ans += n % 10 ; NEW_LINE n = int ( n / 10 ) ; NEW_LINE DEDENT return ans NEW_LINE DEDENT def findInt ( n , m ) : NEW_LINE INDENT minDigit = floor ( m / 9 ) NEW_LINE start = ( int ( pow ( 10 , minDigit ) ) - int ( pow ( 10 , minDigit ) ) % n ) NEW_LINE while ( start < sys . maxsize ) : NEW_LINE INDENT if ( digitSum ( start ) == m ) : NEW_LINE INDENT return start NEW_LINE DEDENT else : NEW_LINE INDENT start += n NEW_LINE DEDENT DEDENT return - 1 NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 13 NEW_LINE m = 32 NEW_LINE print ( findInt ( n , m ) ) NEW_LINE DEDENT