Count of integers obtained by replacing ? in the given string that give remainder 5 when divided by 13 | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MOD  (int)(1e9 + 7) NEW_LINE int modulo_13 ( string s , int n ) { long long dp [ n + 1 ] [ 13 ] = { { 0 } } ; dp [ 0 ] [ 0 ] = 1 ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < 10 ; j ++ ) { int nxt = s [ i ] - '0' ; if ( s [ i ] == ' ? ' ) nxt = j ; for ( int k = 0 ; k < 13 ; k ++ ) { int rem = ( 10 * k + nxt ) % 13 ; dp [ i + 1 ] [ rem ] += dp [ i ] [ k ] ; dp [ i + 1 ] [ rem ] %= MOD ; } if ( s [ i ] != ' ? ' ) break ; } } return ( int ) dp [ n ] [ 5 ] ; } int main ( ) { string s = " ? 44" ; int n = s . size ( ) ; cout << modulo_13 ( s , n ) ; return 0 ; }