عدد التتابعات في السلسلة القابلة للقسمة على n
بالنظر إلى سلسلة مكونة من أرقام من 0 إلى 9، قم بحساب عدد التتابعات فيها القابلة للقسمة على m.
أمثلة:
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
عدد الممارسة الموصى بها من التبعات في سلسلة قابلة للقسمة على nTry It!
يمكن تعريف هذه المشكلة بشكل متكرر. دع باقي السلسلة ذات القيمة x يكون 'r' عند قسمته على n. تؤدي إضافة حرف آخر إلى هذه السلسلة إلى تغيير الباقي إلى (r*10 + newdigit) % n. لكل شخصية جديدة لدينا خياران إما إضافتها في جميع التبعيات الحالية أو تجاهلها. وبالتالي لدينا البنية التحتية الأمثل. يوضح ما يلي نسخة القوة الغاشمة من هذا:
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;
}
يحتوي الحل العودي أعلاه على مشاكل فرعية متداخلة كما هو موضح في شجرة العودية أدناه.
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
C++
وبالتالي يمكننا تطبيق البرمجة الديناميكية. أدناه هو التنفيذ.
Java// C++ program to count subsequences of a // string divisible by n. #includeusing 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 ; } Python 3//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 29AjayKumarC## 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_cJavaScript//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 )); } }
الإخراج4تعقيد الوقت: يا (لين * ن)
المساحة المساعدة : يا (لين * ن)
النهج الفعال: تحسين الفضاءفي النهج السابق موانئ دبي [أنا] [ي] يعتمد على الصف الحالي والسابق من المصفوفة ثنائية الأبعاد. لذا، لتحسين المساحة، نستخدم متجهين درجة حرارة و موانئ دبي التي تتبع الصف الحالي والسابق من موانئ دبي .
خطوات التنفيذ:
- ال countDivisibleSubseq تحسب الدالة عدد التسلسلات الفرعية في سلسلة معينة قابلة للقسمة على رقم معين n.
- يقوم بتهيئة مصفوفة موانئ دبي من الحجم ن لتخزين التهم.
- إنه يتكرر خلال كل رقم من السلسلة ويقوم بتحديث الأعداد الموجودة موانئ دبي على أساس البقايا.
- في كل تكرار، يأخذ في الاعتبار الرقم الحالي والأعداد السابقة لحساب الأعداد المحدثة.
- أخيرًا، تُرجع عدد التبعيات القابلة للقسمة على n المخزنة فيها موانئ دبي[0] .
تطبيق:
C++ #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 // 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 )); } }
Python3 # 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 ))
C# 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 )); } }
JavaScript 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 ));
الإخراج
4
تعقيد الوقت: يا (لين * ن)
المساحة المساعدة : على)
