Data Modelling & AI Data Structure & Algorithm

Count of integers obtained by replacing ? in the given string that give remainder 5 when divided by 13

23 June 2025

0

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 10⁹ + 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>

Output:

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

Time Complexity: O(N * 10 * 13) => O(N)

Auxiliary Space: O(13)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Count of integers obtained by replacing ? in the given string that give remainder 5 when divided by 13

C++

Java

Python3

C#

Javascript

C++

Java

Python3

Javascript

C#

Smarter Retrieval for RAG: Late Chunking with Jina Embeddings v2 and Milvus

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US