Étant donné une chaîne composée de chiffres 0 à 9, comptez le nombre de sous-séquences qu'elle contient divisible par m.
Exemples :
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
Ce problème peut être défini de manière récursive. Laissez le reste d'une chaîne avec la valeur x être « r » lorsqu'il est divisé par n. L'ajout d'un caractère supplémentaire à cette chaîne modifie son reste en (r*10 + newdigit) % n. Pour chaque nouveau personnage, nous avons deux choix : l'ajouter dans toutes les sous-séquences actuelles ou l'ignorer. Nous avons donc une sous-structure optimale. Ce qui suit montre la version force brute de ceci :
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 solution récursive ci-dessus a des sous-problèmes qui se chevauchent, comme le montre l'arbre de récursion ci-dessous.
input string = '330'
(00) ===> at 0th index with 0 remainder
(exclude 0th / (include 0th character)
character) /
(10) (13) ======> at index 1 with 3 as
(E)/ (I) /(E) the current remainder
(20) (23) (23)
|-------|
These two subproblems overlap
Ainsi, nous pouvons appliquer la programmation dynamique. Ci-dessous la mise en œuvre.
// C++ program to count subsequences of a // string divisible by n. #include
//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>
Sortir
4
Complexité temporelle : O(len*n)
Espace Auxiliaire : O(len*n)
Approche efficace : Optimisation de l'espace
Dans l'approche précédente, le dp[i][j] Cela dépend de la ligne actuelle et précédente de la matrice 2D. Donc pour optimiser l'espace nous utilisons deux vecteurs temp. et dp qui gardent une trace de la ligne actuelle et précédente de DP .
Étapes de mise en œuvre :
- Le countDivisibleSubseq La fonction compte le nombre de sous-séquences dans une chaîne donnée str qui sont divisibles par un nombre n donné.
- Il initialise un tableau dp de taille n pour stocker les comptes.
- Il parcourt chaque chiffre de la chaîne et met à jour les comptes dans dp basé sur les restes.
- À chaque itération, il prend en compte le chiffre actuel et les décomptes précédents pour calculer les décomptes mis à jour.
- Enfin, il renvoie le nombre de sous-séquences divisibles par n stockées dans dp[0] .
Mise en œuvre:
C++#include
// 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));
Sortir
4
Complexité temporelle : O(len*n)
Espace Auxiliaire : Sur)