// C++ program to count subsequences of a // string divisible by n. #include   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[lenn];    // 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[ij] += dp[i - 1j];    // include i'th character in all the current  // subsequences of string [0...i-1]  dp[i(j * 10 + (str[i] - '0')) % n] += dp[i - 1j];  }  }    return dp[len - 10];  }   // 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(strn)  {  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>  

#include   using namespace std; int countDivisibleSubseq(string str int n) {  int len = str.length();  int dp[n];  memset(dp 0 sizeof(dp));  dp[(str[0]-'0')%n]++; // Increment the count of remainder of first digit by n  for (int i=1; i<len; i++)  {  int temp[n];  memset(temp 0 sizeof(temp));  temp[(str[i]-'0')%n]++; // Increment the count of remainder of current digit by n  for (int j=0; j<n; j++)  {  temp[j] += dp[j]; // Carry over the counts from previous digit  temp[(j*10 + (str[i]-'0'))%n] += dp[j]; // Update the count with the new remainder formed by appending the current digit  }  for (int j=0; j<n; j++)  {  dp[j] = temp[j]; // Copy the updated counts from temp back to dp for the next iteration  }  }  return dp[0]; // Return the count of subsequences divisible by n } 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. public class GFG {  public static int countDivisibleSubseq(String str int n) {  int length = str.length();  int[] dp = new int[n]; // Create an array of size n to store counts  // Increment the count of remainder of first digit by n  dp[Integer.parseInt(String.valueOf(str.charAt(0))) % n] += 1;  for (int i = 1; i < length; i++) {  int[] temp = new int[n]; // Create a temporary array of size n  // Increment the count of remainder of current digit by n  temp[Integer.parseInt(String.valueOf(str.charAt(i))) % n] += 1;  for (int j = 0; j < n; j++) {  temp[j] += dp[j]; // Carry over the counts from the previous digit  // Calculate the new remainder  int newRemainder = (j * 10 + Integer.parseInt(String.valueOf(str.charAt(i)))) % n;  // Update the count with the new remainder  temp[newRemainder] += dp[j];  }  dp = temp;  }  return dp[0];  } //Driver code  public static void main(String[] args) {  String str = '1234';  int n = 4;  System.out.println(countDivisibleSubseq(str n));  } } 

# Python 3 program to count subsequences # of a string divisible by n. def countDivisibleSubseq(str n): length = len(str) dp = [0] * n # Create an array of size n # Increment the count of remainder of first digit by n dp[int(str[0]) % n] += 1 for i in range(1 length): temp = [0] * n # Create a temporary array of size n # Increment the count of remainder of current digit by n temp[int(str[i]) % n] += 1 for j in range(n): temp[j] += dp[j] # Carry over the counts from the previous digit # Calculate the new remainder new_remainder = (j * 10 + int(str[i])) % n # Update the count with the new remainder temp[new_remainder] += dp[j] dp = temp return dp[0] # Driver code str = '1234' n = 4 print(countDivisibleSubseq(str n)) 

using System; class GFG {  static int CountDivisibleSubseq(string str int n)  {  int len = str.Length;  int[] dp = new int[n];  Array.Fill(dp 0);  dp[(str[0] - '0')  % n]++; // Increment the count of remainder of  // first digit by n  for (int i = 1; i < len; i++) {  int[] temp = new int[n];  Array.Fill(temp 0);  temp[(str[i] - '0')  % n]++; // Increment the count of remainder  // of current digit by n  for (int j = 0; j < n; j++) {  temp[j] += dp[j]; // Carry over the counts  // from previous digit  temp[(j * 10 + (str[i] - '0')) % n]  += dp[j]; // Update the count with the  // new remainder formed by  // appending the current digit  }  for (int j = 0; j < n; j++) {  dp[j] = temp[j]; // Copy the updated counts  // from temp back to dp for  // the next iteration  }  }  return dp[0]; // Return the count of subsequences  // divisible by n  }  static void Main()  {  string str = '1234';  int n = 4;  Console.WriteLine(CountDivisibleSubseq(str n));  } } 

function countDivisibleSubseq(str n) {  const len = str.length;  const dp = new Array(n).fill(0);    // Increment the count of remainder of first digit by n  dp[Number(str[0]) % n]++;   for (let i = 1; i < len; i++) {  const temp = new Array(n).fill(0);    // Increment the count of remainder of current digit by n  temp[Number(str[i]) % n]++;  for (let j = 0; j < n; j++) {  temp[j] += dp[j]; // Carry over the counts from previous digit  // Update the count with the new remainder   // formed by appending the current digit  temp[(j * 10 + Number(str[i])) % n] += dp[j];   }  for (let j = 0; j < n; j++) {  // Copy the updated counts from   // temp back to dp for the next iteration  dp[j] = temp[j];   }  }  return dp[0]; // Return the count of subsequences divisible by n } const str = '1234'; const n = 4; console.log(countDivisibleSubseq(str n));