Número de subsecuencias en una string divisible por n

Dada una string que consta de dígitos 0-9, cuente el número de subsecuencias en ella divisible por m.
Ejemplos: 
 

Input  : str = "1234", n = 4
Output : 4
The subsequences 4, 12, 24 and 124 are 
divisible by 4.
 
Input  : str = "330", n = 6
Output : 4
The subsequences 30, 30, 330 and 0 are 
divisible by n.

Input  : str = "676", n = 6
Output : 3
The subsequences 6, 6 and 66

Este problema se puede definir recursivamente. Deje que el resto de una string con valor x sea ‘r’ cuando se divide por n. Agregar un carácter más a esta string cambia su resto a (r*10 + nuevo dígito) % n. Para cada carácter nuevo, tenemos dos opciones, agregarlo en todas las subsecuencias actuales o ignorarlo. Por lo tanto, tenemos una subestructura óptima. A continuación se muestra la versión de fuerza bruta de esto:
 

string str = "330";
int n = 6

// idx is value of current index in str
// rem is current remainder
int count(int idx, int rem)
{
    // If last character reached
    if (idx == n)
        return (rem == 0)? 1 : 0;

    int ans = 0;

    // we exclude it, thus remainder
    // remains the same
    ans += count(idx+1, rem);

    // we include it and thus new remainder
    ans += count(idx+1, (rem*10 + str[idx]-'0')%n);

    return ans;
}

La solución recursiva anterior tiene subproblemas superpuestos como se muestra en el árbol de recursividad a continuación.
 

          input string = "330"
             (0,0) ===> at 0th index with 0 remainder
(exclude 0th /      (include 0th character)
 character) /      
       (1,0)      (1,3) ======> at index 1 with 3 as 
      (E)/  (I)     /(E)       the current remainder
     (2,0)  (2,3)   (2,3)
             |-------|
     These two subproblems overlap  

Así, podemos aplicar la Programación Dinámica. A continuación se muestra la implementación.
 

// C++ program to count subsequences of a
// string divisible by n.
#include<bits/stdc++.h>
using namespace std;
 
// Returns count of subsequences of str
// divisible by n.
int countDivisibleSubseq(string str, int n)
{
    int len = str.length();
 
    // division by n can leave only n remainder
    // [0..n-1]. dp[i][j] indicates number of
    // subsequences in string [0..i] which leaves
    // remainder j after division by n.
    int dp[len][n];
    memset(dp, 0, sizeof(dp));
 
    // Filling value for first digit in str
    dp[0][(str[0]-'0')%n]++;
 
    for (int i=1; i<len; i++)
    {
        // start a new subsequence with index i
        dp[i][(str[i]-'0')%n]++;
 
        for (int j=0; j<n; j++)
        {
            // exclude i'th character from all the
            // current subsequences of string [0...i-1]
            dp[i][j] += dp[i-1][j];
 
            // include i'th character in all the current
            // subsequences of string [0...i-1]
            dp[i][(j*10 + (str[i]-'0'))%n] += dp[i-1][j];
        }
    }
 
    return dp[len-1][0];
}
 
// Driver code
int main()
{
    string str = "1234";
    int n = 4;
    cout << countDivisibleSubseq(str, n);
    return 0;
}

//Java program to count subsequences of a
// string divisible by n
 
class GFG {
 
// Returns count of subsequences of str
// divisible by n.
    static int countDivisibleSubseq(String str, int n) {
        int len = str.length();
 
        // division by n can leave only n remainder
        // [0..n-1]. dp[i][j] indicates number of
        // subsequences in string [0..i] which leaves
        // remainder j after division by n.
        int dp[][] = new int[len][n];
 
        // Filling value for first digit in str
        dp[0][(str.charAt(0) - '0') % n]++;
 
        for (int i = 1; i < len; i++) {
            // start a new subsequence with index i
            dp[i][(str.charAt(i) - '0') % n]++;
 
            for (int j = 0; j < n; j++) {
                // exclude i'th character from all the
                // current subsequences of string [0...i-1]
                dp[i][j] += dp[i - 1][j];
 
                // include i'th character in all the current
                // subsequences of string [0...i-1]
                dp[i][(j * 10 + (str.charAt(i) - '0')) % n] += dp[i - 1][j];
            }
        }
 
        return dp[len - 1][0];
    }
 
// Driver code
    public static void main(String[] args) {
        String str = "1234";
        int n = 4;
        System.out.print(countDivisibleSubseq(str, n));
    }
}
// This code is contributed by 29AjayKumar

# Python 3 program to count subsequences
# of a string divisible by n.
 
# Returns count of subsequences of
# str divisible by n.
def countDivisibleSubseq(str, n):
    l = len(str)
 
    # division by n can leave only n remainder
    # [0..n-1]. dp[i][j] indicates number of
    # subsequences in string [0..i] which leaves
    # remainder j after division by n.
    dp = [[0 for x in range(l)]
             for y in range(n)]
 
    # Filling value for first digit in str
    dp[int(str[0]) % n][0] += 1
      
    for i in range(1, l):
       
       # start a new subsequence with index i
        dp[int(str[i]) % n][i] += 1
 
        for j in range(n):
 
          # exclude i'th character from all the
          # current subsequences of string [0...i-1]
          dp[j][i] += dp[j][i-1]
 
          # include i'th character in all the current
          # subsequences of string [0...i-1]
          dp[(j * 10 + int(str[i])) % n][i] += dp[j][i-1]
 
    return dp[0][l-1]
 
# Driver code
if __name__ == "__main__":
     
    str = "1234"
    n = 4
    print(countDivisibleSubseq(str, n))
 
# This code is contributed by ita_c

//C# program to count subsequences of a
// string divisible by n
  
using System;
class GFG {
  
// Returns count of subsequences of str
// divisible by n.
    static int countDivisibleSubseq(string str, int n) {
        int len = str.Length;
  
        // division by n can leave only n remainder
        // [0..n-1]. dp[i][j] indicates number of
        // subsequences in string [0..i] which leaves
        // remainder j after division by n.
        int[,] dp = new int[len,n];
  
        // Filling value for first digit in str
        dp[0,(str[0] - '0') % n]++;
  
        for (int i = 1; i < len; i++) {
            // start a new subsequence with index i
            dp[i,(str[i] - '0') % n]++;
  
            for (int j = 0; j < n; j++) {
                // exclude i'th character from all the
                // current subsequences of string [0...i-1]
                dp[i,j] += dp[i - 1,j];
  
                // include i'th character in all the current
                // subsequences of string [0...i-1]
                dp[i,(j * 10 + (str[i] - '0')) % n] += dp[i - 1,j];
            }
        }
  
        return dp[len - 1,0];
    }
  
// Driver code
    public static void Main() {
        String str = "1234";
        int n = 4;
        Console.Write(countDivisibleSubseq(str, n));
    }
}

<script>
//Javascript program to count subsequences of a
// string divisible by n
     
    // Returns count of subsequences of str
    // divisible by n.
    function countDivisibleSubseq(str,n)
    {
        let len = str.length;
   
        // division by n can leave only n remainder
        // [0..n-1]. dp[i][j] indicates number of
        // subsequences in string [0..i] which leaves
        // remainder j after division by n.
        let dp = new Array(len);
        for(let i = 0; i < len; i++)
        {
            dp[i] = new Array(n);
            for(let j = 0; j < n; j++)
            {
                dp[i][j] = 0;
            }
        }
   
        // Filling value for first digit in str
        dp[0][(str[0] - '0') % n]++;
   
        for (let i = 1; i < len; i++) {
            // start a new subsequence with index i
            dp[i][(str[i] - '0') % n]++;
   
            for (let j = 0; j < n; j++) {
                // exclude i'th character from all the
                // current subsequences of string [0...i-1]
                dp[i][j] += dp[i - 1][j];
   
                // include i'th character in all the current
                // subsequences of string [0...i-1]
                dp[i][(j * 10 + (str[i] - '0')) % n] += dp[i - 1][j];
            }
        }
   
        return dp[len - 1][0];
    }
     
    // Driver code
    let str = "1234";
    let n = 4;
    document.write(countDivisibleSubseq(str, n));
     
    // This code is contributed by avanitrachhadiya2155
</script>

4

Complejidad de Tiempo: O(len * n) 
Espacio Auxiliar : O(len * n)

Este artículo es una contribución de Ekta Goel . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.