Count numbers in a range with digit sum divisible by K having first and last digit different | Python3 program to count numbers in a range with digit sum divisible by K having first and last digit different ; For calculating the upper bound of the sequence . ; Checking whether the sum of digits = 0 or not and the corner case as number equal to 1 ; If the state is visited then return the answer of this state directly . ; For checking whether digit to be placed is up to upper bound at the position pos or upto 9 ; Calculating new digit sum modulo k ; Check if there is a prefix of 0 s and current digit != 0 ; Then current digit will be the starting digit ; Update the boolean flag that the starting digit has been found ; At n - 1 , check if current digit and starting digit are the same then no need to calculate this answer ; Else find the answer ; Function to find the required count ; Setting up the upper bound ; calculating F ( R ) ; Setting up the upper bound ; Calculating F ( L - 1 ) ; Driver code
K = 0 NEW_LINE N = 0 NEW_LINE v = [ ] NEW_LINE dp = [ [ [ [ [ - 1 for i in range ( 2 ) ] for j in range ( 2 ) ] for k in range ( 10 ) ] for l in range ( 1000 ) ] for m in range ( 20 ) ] NEW_LINE def init ( x ) : NEW_LINE INDENT global K NEW_LINE global N NEW_LINE global v NEW_LINE v = [ ] NEW_LINE while ( x > 0 ) : NEW_LINE INDENT v . append ( x % 10 ) NEW_LINE x //= 10 NEW_LINE DEDENT v = v [ : : - 1 ] NEW_LINE N = len ( v ) NEW_LINE DEDENT def fun ( pos , sum , st , check , f ) : NEW_LINE INDENT global N NEW_LINE global v NEW_LINE if ( pos == N ) : NEW_LINE INDENT return ( sum == 0 and check == 1 ) NEW_LINE DEDENT if ( dp [ pos ] [ sum ] [ st ] [ check ] [ f ] != - 1 ) : NEW_LINE INDENT return dp [ pos ] [ sum ] [ st ] [ check ] [ f ] NEW_LINE DEDENT lmt = 9 NEW_LINE if ( f == False ) : NEW_LINE INDENT lmt = v [ pos ] NEW_LINE DEDENT ans = 0 NEW_LINE for digit in range ( lmt + 1 ) : NEW_LINE INDENT nf = f NEW_LINE new_sum = ( sum + digit ) % K NEW_LINE new_check = check NEW_LINE new_st = st NEW_LINE if ( f == 0 and digit < lmt ) : NEW_LINE INDENT nf = 1 NEW_LINE DEDENT if ( check == 0 and digit != 0 ) : NEW_LINE INDENT new_st = digit NEW_LINE new_check = 1 NEW_LINE DEDENT if ( pos == N - 1 and new_st == digit ) : NEW_LINE INDENT continue NEW_LINE DEDENT ans += fun ( pos + 1 , new_sum , new_st , new_check , nf ) NEW_LINE dp [ pos ] [ sum ] [ st ] [ check ] [ f ] = ans NEW_LINE DEDENT return ans NEW_LINE DEDENT def findCount ( L , R , K ) : NEW_LINE INDENT init ( R ) NEW_LINE r_ans = fun ( 0 , 0 , 0 , 0 , 0 ) NEW_LINE init ( L - 1 ) NEW_LINE r_ans = 0 NEW_LINE l_ans = fun ( 0 , 0 , 0 , 0 , 0 ) NEW_LINE print ( l_ans - r_ans ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT L = 10 NEW_LINE R = 20 NEW_LINE K = 2 NEW_LINE findCount ( L , R , K ) NEW_LINE DEDENT