Count of integers obtained by replacing ? in the given string that give remainder 5 when divided by 13
Given string str of length N. The task is to find the number of integers obtained by replacing ‘?’ with any digit such that the formed integer gives remainder 5 when it is divided by 13.
Numbers can also begin with zero. The answer can be very large, so, output answer modulo 109 + 7.
Examples:
Input: str = “?44”
Output: 1
Only possible number is 044
Input: str = “7?4”
Output: 0
Input: str = “8?3?4233?4?”
Output: 770
Approach: Let dp[i][j] be the number of ways to create an i-digit number consistent with the first i digits of the given pattern and congruent to j modulo 13. As our base case, dp[0][i]=0 for i from 1 to 12, and dp[0][0]=1 (as our length-zero number has value zero and thus is zero mod 13.)
Notice that appending a digit k to the end of a number that’s j mod 13 gives a number that’s congruent to 10j+k mod 13. We use this fact to perform our transitions. For every state, dp[i][j] with i < N, iterate over the possible values of k. (If s[i]=’?’, there will be ten choices for k, and otherwise, there will only be one choice.) Then, we add dp[i][j] to dp[i+1][(10j+k)%13].
To get our final answer, we can simply print dp[N][5].
Below is the implementation of the above approach :
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; #define MOD (int)(1e9 + 7) // 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 int modulo_13(string s, int n) { long long dp[n + 1][13] = { { 0 } }; // Initialise dp[0][0] = 1; for ( int i = 0; i < n; i++) { for ( int j = 0; j < 10; j++) { int nxt = s[i] - '0' ; // Place digit j at ? position if (s[i] == '?' ) nxt = j; // Get the remainder 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 the required answer return ( int )dp[n][5]; } // Driver code int main() { string s = "?44" ; int n = s.size(); cout << modulo_13(s, n); return 0; } |
Java
// Java implementation of the approach class GFG { static int MOD = ( int )(1e9 + 7 ); // 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 static int modulo_13(String s, int n) { long [][]dp = new long [n + 1 ][ 13 ]; // Initialise dp[ 0 ][ 0 ] = 1 ; for ( int i = 0 ; i < n; i++) { for ( int j = 0 ; j < 10 ; j++) { int nxt = s.charAt(i) - '0' ; // Place digit j at ? position if (s.charAt(i) == '?' ) nxt = j; // Get the remainder 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.charAt(i) != '?' ) break ; } } // Return the required answer return ( int )dp[n][ 5 ]; } // Driver code public static void main(String []args) { String s = "?44" ; int n = s.length(); System.out.println(modulo_13(s, n)); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach import numpy as np MOD = ( int )( 1e9 + 7 ) # 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 def modulo_13(s, n) : dp = np.zeros((n + 1 , 13 )); # Initialise dp[ 0 ][ 0 ] = 1 ; for i in range (n) : for j in range ( 10 ) : nxt = ord (s[i]) - ord ( '0' ); # Place digit j at ? position if (s[i] = = '?' ) : nxt = j; # Get the remainder for k in range ( 13 ) : rem = ( 10 * k + nxt) % 13 ; dp[i + 1 ][rem] + = dp[i][k]; dp[i + 1 ][rem] % = MOD; if (s[i] ! = '?' ) : break ; # Return the required answer return int (dp[n][ 5 ]); # Driver code if __name__ = = "__main__" : s = "?44" ; n = len (s); print (modulo_13(s, n)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approach using System; class GFG { static int MOD = ( int )(1e9 + 7); // 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 static int modulo_13(String s, int n) { long [,]dp = new long [n + 1, 13]; // Initialise dp[0, 0] = 1; for ( int i = 0; i < n; i++) { for ( int j = 0; j < 10; j++) { int nxt = s[i] - '0' ; // Place digit j at ? position if (s[i] == '?' ) nxt = j; // Get the remainder 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 the required answer return ( int )dp[n,5]; } // Driver code public static void Main(String []args) { String s = "?44" ; int n = s.Length; Console.WriteLine(modulo_13(s, n)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // javascript implementation of the approach var MOD = parseInt(1e9 + 7); // 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 function modulo_13( s , n) { var dp = Array(n + 1).fill().map(()=>Array(13).fill(0)); // Initialise dp[0][0] = 1; for (i = 0; i < n; i++) { for (j = 0; j < 10; j++) { var nxt = s.charAt(i) - '0' ; // Place digit j at ? position if (s.charAt(i) == '?' ) nxt = j; // Get the remainder for (k = 0; k < 13; k++) { var rem = (10 * k + nxt) % 13; dp[i + 1][rem] += dp[i][k]; dp[i + 1][rem] %= MOD; } if (s.charAt(i) != '?' ) break ; } } // Return the required answer return parseInt( dp[n][5]); } // Driver code var s = "?44" ; var n = s.length; document.write(modulo_13(s, n)); // This code contributed by aashish1995 </script> |
1
Time Complexity: O(100 * N)
Auxiliary Space: O(100 * N)
Efficient Approach : Space Optimization
In this approach we use a 1D array dp of length 13 instead a 2D matrix of length 100*N instead, which stores only the counts of remainders for the current position. This reduces the space complexity to O(13)
Implementation Steps:
- Initialize an array dp of length 13 to store the counts of remainders for the current position. Set dp[0] to 1.
- If the current character is ?, initialize an array nxt to indicate that all digits 0-9 are valid choices for the current position. Otherwise, set nxt to contain only the digit indicated by the current character.
- Initialize a new array dp_new to store the updated counts of remainders for the next position.
- For each remainder j in the current dp array, iterate over each valid digit k indicated by the nxt array.
- Compute the remainder obtained by appending digit k to the remainder j.
- Add the count of remainders for remainder j in the current dp array to the count of remainders for the new remainder rem in the dp_new array.
- Take the modulo of the sum.
- Copy the dp_new array into the dp array using the memcpy function.
- After iterating over all characters in the input string s, return the count of remainders for remainder 5 in the final dp array.
Implementation:
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; #define MOD (int)(1e9 + 7) // 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 int modulo_13(string s, int n) { // initialize DP with 0 int dp[13] = { 0 }; // Base Case dp[0] = 1; for ( int i = 0; i < n; i++) { int nxt[10] = { 0 }; // Place digit j at ? position if (s[i] == '?' ) { for ( int j = 0; j < 10; j++) nxt[j] = 1; } else { nxt[s[i] - '0' ] = 1; } // iterate over subproblems to get the current // from previous computaton int dp_new[13] = { 0 }; for ( int j = 0; j < 13; j++) { for ( int k = 0; k < 10; k++) { if (!nxt[k]) continue ; int rem = (10 * j + k) % 13; // Get the remainder dp_new[rem] += dp[j]; dp_new[rem] %= MOD; } } // assigning values for further iterations memcpy (dp, dp_new, sizeof (dp)); } // Return the required answer return dp[5]; } // Driver Code int main() { string s = "?44" ; int n = s.size(); // function call cout << modulo_13(s, n); return 0; } |
Java
import java.util.*; public class Main { static final int MOD = ( int )(1e9 + 7 ); // 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 public static int modulo_13(String s, int n) { // initialize DP with 0 int [] dp = new int [ 13 ]; // Base Case dp[ 0 ] = 1 ; for ( int i = 0 ; i < n; i++) { int [] nxt = new int [ 10 ]; // Place digit j at ? position if (s.charAt(i) == '?' ) { for ( int j = 0 ; j < 10 ; j++) nxt[j] = 1 ; } else { nxt[s.charAt(i) - '0' ] = 1 ; } // iterate over subproblems to get the current // from previous computaton int [] dp_new = new int [ 13 ]; for ( int j = 0 ; j < 13 ; j++) { for ( int k = 0 ; k < 10 ; k++) { if (nxt[k] == 0 ) continue ; int rem = ( 10 * j + k) % 13 ; // Get the remainder dp_new[rem] += dp[j]; dp_new[rem] %= MOD; } } // assigning values for further iterations System.arraycopy(dp_new, 0 , dp, 0 , dp.length); } // Return the required answer return dp[ 5 ]; } // Driver Code public static void main(String[] args) { String s = "?44" ; int n = s.length(); // function call System.out.println(modulo_13(s, n)); } } |
Python3
MOD = int ( 1e9 + 7 ) # 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 def modulo_13(s): n = len (s) # initialize DP with 0 dp = [ 0 ] * 13 # Base Case dp[ 0 ] = 1 for i in range (n): nxt = [ 0 ] * 10 # Place digit j at ? position if s[i] = = '?' : nxt = [ 1 ] * 10 else : nxt[ int (s[i])] = 1 # iterate over subproblems to get the current # from previous computaton dp_new = [ 0 ] * 13 for j in range ( 13 ): for k in range ( 10 ): if not nxt[k]: continue rem = ( 10 * j + k) % 13 # Get the remainder dp_new[rem] + = dp[j] dp_new[rem] % = MOD # assigning values for further iterations dp = dp_new[:] # Return the required answer return dp[ 5 ] # Driver Code s = "?44" # function call print (modulo_13(s)) |
Javascript
const MOD = 1e9 + 7; // 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 function modulo_13(s, n) { // initialize DP with 0 let dp = new Array(13).fill(0); // Base Case dp[0] = 1; for (let i = 0; i < n; i++) { let nxt = new Array(10).fill(0); // Place digit j at ? position if (s[i] == '?' ) { for (let j = 0; j < 10; j++) nxt[j] = 1; } else { nxt[s[i] - '0' ] = 1; } // iterate over subproblems to get the current // from previous computaton let dp_new = new Array(13).fill(0); for (let j = 0; j < 13; j++) { for (let k = 0; k < 10; k++) { if (!nxt[k]) continue ; let rem = (10 * j + k) % 13; // Get the remainder dp_new[rem] += dp[j]; dp_new[rem] %= MOD; } } // assigning values for further iterations dp = [...dp_new]; } // Return the required answer return dp[5]; } let s = "?44" ; let n = s.length; // function call console.log(modulo_13(s, n)); |
C#
// C# program for above approach using System; public class Program { // 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 const int MOD = ( int )(1e9 + 7); public static int Modulo13( string s, int n) { // initialize DP with 0 int [] dp = new int [13]; // Base Case dp[0] = 1; for ( int i = 0; i < n; i++) { int [] nxt = new int [10]; // Place digit j at ? position if (s[i] == '?' ) { for ( int j = 0; j < 10; j++) nxt[j] = 1; } else { nxt[s[i] - '0' ] = 1; } // iterate over subproblems to get the current // from previous computaton int [] dp_new = new int [13]; for ( int j = 0; j < 13; j++) { for ( int k = 0; k < 10; k++) { if (nxt[k] == 0) continue ; int rem = (10 * j + k) % 13; // Get the remainder dp_new[rem] += dp[j]; dp_new[rem] %= MOD; } } // assigning values for further iterations Array.Copy(dp_new, dp, dp_new.Length); } // Return the required answer return dp[5]; } // Driver Code public static void Main() { string s = "?44" ; int n = s.Length; // function call Console.WriteLine(Modulo13(s, n)); } } |
Output
1
Time Complexity: O(N * 10 * 13) => O(N)
Auxiliary Space: O(13)
Contact Us