Gegeven een reeks bestaande uit de cijfers 0-9, tel het aantal deelreeksen daarin dat deelbaar is door m.
Voorbeelden:
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
Dit probleem kan recursief worden gedefinieerd. Laat de rest van een string met waarde x 'r' zijn wanneer gedeeld door n. Als u nog een teken aan deze tekenreeks toevoegt, verandert de rest ervan in (r*10 + nieuwcijfer) % n. Voor elk nieuw personage hebben we twee keuzes: voeg het toe aan alle huidige subreeksen of negeer het. Zo hebben we een optimale onderbouw. Het volgende toont de brute force-versie hiervan:
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;
}
De bovenstaande recursieve oplossing heeft overlappende subproblemen, zoals weergegeven in de onderstaande recursieboom.
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
Zo kunnen we dynamisch programmeren toepassen. Hieronder vindt u de implementatie.
// 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>
Uitvoer
4
Tijdcomplexiteit: O(len * n)
Hulpruimte: O(len * n)
Efficiënte aanpak: Ruimteoptimalisatie
In de vorige benadering werd de dp[i][j] is afhankelijk van de huidige en vorige rij 2D-matrix. Om de ruimte te optimaliseren gebruiken we dus twee vectoren temperatuur En dp die de huidige en vorige rij bijhouden DP .
Implementatiestappen:
- De tellenDeelbaarVervolg functie telt het aantal subreeksen in een gegeven string str die deelbaar zijn door een bepaald getal n.
- Het initialiseert een array dp van grootte N tellingen op te slaan.
- Het doorloopt elk cijfer van de string en werkt de tellingen bij dp gebaseerd op restanten.
- Bij elke iteratie wordt rekening gehouden met het huidige cijfer en de voorgaande tellingen om de bijgewerkte tellingen te berekenen.
- Ten slotte retourneert het het aantal deelreeksen dat deelbaar is door n, opgeslagen in dp[0] .
Uitvoering:
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));
Uitvoer
4
Tijdcomplexiteit: O(len * n)
Hulpruimte: Op)