Count of integers obtained by replacing ? in the given string that give remainder 5 when divided by 13 | Python3 implementation of the approach ; Function to find the count of integers obtained by replacing ' ? ' in a given string such that formed integer gives remainder 5 when it is divided by 13 ; Initialise ; Place digit j at ? position ; Get the remainder ; Return the required answer ; Driver code
import numpy as np NEW_LINE MOD = ( int ) ( 1e9 + 7 ) NEW_LINE def modulo_13 ( s , n ) : NEW_LINE INDENT dp = np . zeros ( ( n + 1 , 13 ) ) ; NEW_LINE dp [ 0 ] [ 0 ] = 1 ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( 10 ) : NEW_LINE INDENT nxt = ord ( s [ i ] ) - ord ( '0' ) ; NEW_LINE if ( s [ i ] == ' ? ' ) : NEW_LINE INDENT nxt = j ; NEW_LINE DEDENT for k in range ( 13 ) : NEW_LINE INDENT rem = ( 10 * k + nxt ) % 13 ; NEW_LINE dp [ i + 1 ] [ rem ] += dp [ i ] [ k ] ; NEW_LINE dp [ i + 1 ] [ rem ] %= MOD ; NEW_LINE DEDENT if ( s [ i ] != ' ? ' ) : NEW_LINE INDENT break ; NEW_LINE DEDENT DEDENT DEDENT return int ( dp [ n ] [ 5 ] ) ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT s = " ? 44" ; NEW_LINE n = len ( s ) ; NEW_LINE print ( modulo_13 ( s , n ) ) ; NEW_LINE DEDENT