Divisibilité des sous-chaînes par 11 requêtes
Étant donné un grand nombre n (ayant des chiffres jusqu'à 10 ^ 6) et diverses requêtes de la forme ci-dessous :
Query(l r) : find if the sub-string between the indices l and r (Both inclusive) are divisible by 11.
Exemples :
Input: n = 122164154695 Queries: l = 0 r = 3 l = 1 r = 2 l = 5 r = 9 l = 0 r = 11 Output: True False False True Explanation: In the first query 1221 is divisible by 11 In the second query 22 is divisible by 11 and so on.
Nous savons que tout nombre est divisible par 11 si la différence entre la somme des chiffres impairs indexés et la somme des chiffres pairs indexés est divisible par 11, c'est-à-dire
Somme (chiffres aux endroits impairs) - La somme (chiffres aux endroits pairs) doit être divisible par 11 .
L'idée est donc de prétraiter un tableau auxiliaire qui stockerait la somme des chiffres aux endroits pairs et impairs.
Pour évaluer une requête, nous pouvons utiliser le tableau auxiliaire pour y répondre en O(1).
// C++ program to check divisibility by 11 in // substrings of a number string #include using namespace std ; const int MAX = 1000005 ; // To store sums of even and odd digits struct OddEvenSums { // Sum of even placed digits int e_sum ; // Sum of odd placed digits int o_sum ; }; // Auxiliary array OddEvenSums sum [ MAX ]; // Utility function to evaluate a character's // integer value int toInt ( char x ) { return int ( x ) - 48 ; } // This function receives the string representation // of the number and precomputes the sum array void preCompute ( string x ) { // Initialize everb sum [ 0 ]. e_sum = sum [ 0 ]. o_sum = 0 ; // Add the respective digits depending on whether // they're even indexed or odd indexed for ( int i = 0 ; i < x . length (); i ++ ) { if ( i % 2 == 0 ) { sum [ i + 1 ]. e_sum = sum [ i ]. e_sum + toInt ( x [ i ]); sum [ i + 1 ]. o_sum = sum [ i ]. o_sum ; } else { sum [ i + 1 ]. o_sum = sum [ i ]. o_sum + toInt ( x [ i ]); sum [ i + 1 ]. e_sum = sum [ i ]. e_sum ; } } } // This function receives l and r representing // the indices and prints the required output bool query ( int l int r ) { int diff = ( sum [ r + 1 ]. e_sum - sum [ r + 1 ]. o_sum ) - ( sum [ l ]. e_sum - sum [ l ]. o_sum ); return ( diff % 11 == 0 ); } //driver function to check the program int main () { string s = '122164154695' ; preCompute ( s ); cout < < query ( 0 3 ) < < endl ; cout < < query ( 1 2 ) < < endl ; cout < < query ( 5 9 ) < < endl ; cout < < query ( 0 11 ) < < endl ; return 0 ; }
Java // Java program to check divisibility by 11 in // subStrings of a number String class GFG { static int MAX = 1000005 ; // To store sums of even and odd digits static class OddEvenSums { // Sum of even placed digits int e_sum ; // Sum of odd placed digits int o_sum ; }; // Auxiliary array static OddEvenSums [] sum = new OddEvenSums [ MAX ] ; // Utility function to evaluate a character's // integer value static int toInt ( char x ) { return x - 48 ; } // This function receives the String representation // of the number and precomputes the sum array static void preCompute ( String x ) { // Initialize everb sum [ 0 ] . e_sum = sum [ 0 ] . o_sum = 0 ; // Add the respective digits depending on whether // they're even indexed or odd indexed for ( int i = 0 ; i < x . length (); i ++ ) { if ( i % 2 == 0 ) { sum [ i + 1 ] . e_sum = sum [ i ] . e_sum + toInt ( x . charAt ( i )); sum [ i + 1 ] . o_sum = sum [ i ] . o_sum ; } else { sum [ i + 1 ] . o_sum = sum [ i ] . o_sum + toInt ( x . charAt ( i )); sum [ i + 1 ] . e_sum = sum [ i ] . e_sum ; } } } // This function receives l and r representing // the indices and prints the required output static boolean query ( int l int r ) { int diff = ( sum [ r + 1 ] . e_sum - sum [ r + 1 ] . o_sum ) - ( sum [ l ] . e_sum - sum [ l ] . o_sum ); return ( diff % 11 == 0 ); } //driver function to check the program public static void main ( String [] args ) { for ( int i = 0 ; i < MAX ; i ++ ) { sum [ i ] = new OddEvenSums (); } String s = '122164154695' ; preCompute ( s ); System . out . println ( query ( 0 3 ) ? 1 : 0 ); System . out . println ( query ( 1 2 ) ? 1 : 0 ); System . out . println ( query ( 5 9 ) ? 1 : 0 ); System . out . println ( query ( 0 11 ) ? 1 : 0 ); } } // This code is contributed by Rajput-Ji
Python3 # Python3 program to check divisibility by # 11 in subStrings of a number String MAX = 1000005 # To store sums of even and odd digits class OddEvenSums : def __init__ ( self e_sum o_sum ): # Sum of even placed digits self . e_sum = e_sum # Sum of odd placed digits self . o_sum = o_sum sum = [ OddEvenSums ( 0 0 ) for i in range ( MAX )] # This function receives the String # representation of the number and # precomputes the sum array def preCompute ( x ): # Initialize everb sum [ 0 ] . e_sum = sum [ 0 ] . o_sum = 0 # Add the respective digits # depending on whether # they're even indexed or # odd indexed for i in range ( len ( x )): if ( i % 2 == 0 ): sum [ i + 1 ] . e_sum = ( sum [ i ] . e_sum + int ( x [ i ])) sum [ i + 1 ] . o_sum = sum [ i ] . o_sum else : sum [ i + 1 ] . o_sum = ( sum [ i ] . o_sum + int ( x [ i ])) sum [ i + 1 ] . e_sum = sum [ i ] . e_sum # This function receives l and r representing # the indices and prints the required output def query ( l r ): diff = (( sum [ r + 1 ] . e_sum - sum [ r + 1 ] . o_sum ) - ( sum [ l ] . e_sum - sum [ l ] . o_sum )) if ( diff % 11 == 0 ): return True else : return False # Driver code if __name__ == '__main__' : s = '122164154695' preCompute ( s ) print ( 1 if query ( 0 3 ) else 0 ) print ( 1 if query ( 1 2 ) else 0 ) print ( 1 if query ( 5 9 ) else 0 ) print ( 1 if query ( 0 11 ) else 0 ) # This code is contributed by rutvik_56
C# // C# program to check // divisibility by 11 in // subStrings of a number String using System ; class GFG { static int MAX = 1000005 ; // To store sums of even // and odd digits public class OddEvenSums { // Sum of even placed digits public int e_sum ; // Sum of odd placed digits public int o_sum ; }; // Auxiliary array static OddEvenSums [] sum = new OddEvenSums [ MAX ]; // Utility function to // evaluate a character's // integer value static int toInt ( char x ) { return x - 48 ; } // This function receives the // String representation of the // number and precomputes the sum array static void preCompute ( String x ) { // Initialize everb sum [ 0 ]. e_sum = sum [ 0 ]. o_sum = 0 ; // Add the respective digits // depending on whether they're // even indexed or odd indexed for ( int i = 0 ; i < x . Length ; i ++ ) { if ( i % 2 == 0 ) { sum [ i + 1 ]. e_sum = sum [ i ]. e_sum + toInt ( x [ i ]); sum [ i + 1 ]. o_sum = sum [ i ]. o_sum ; } else { sum [ i + 1 ]. o_sum = sum [ i ]. o_sum + toInt ( x [ i ]); sum [ i + 1 ]. e_sum = sum [ i ]. e_sum ; } } } // This function receives l and r // representing the indices and // prints the required output static bool query ( int l int r ) { int diff = ( sum [ r + 1 ]. e_sum - sum [ r + 1 ]. o_sum ) - ( sum [ l ]. e_sum - sum [ l ]. o_sum ); return ( diff % 11 == 0 ); } // Driver function to check the program public static void Main ( String [] args ) { for ( int i = 0 ; i < MAX ; i ++ ) { sum [ i ] = new OddEvenSums (); } String s = '122164154695' ; preCompute ( s ); Console . WriteLine ( query ( 0 3 ) ? 1 : 0 ); Console . WriteLine ( query ( 1 2 ) ? 1 : 0 ); Console . WriteLine ( query ( 5 9 ) ? 1 : 0 ); Console . WriteLine ( query ( 0 11 ) ? 1 : 0 ); } } // This code is contributed by gauravrajput1
JavaScript < script > // Javascript program to check divisibility by 11 in // subStrings of a number String let MAX = 1000005 ; // To store sums of even and odd digits class OddEvenSums { constructor () { this . e_sum = 0 ; this . o_sum = 0 ; } } // Auxiliary array let sum = new Array ( MAX ); // Utility function to evaluate a character's // integer value function toInt ( x ) { return x . charCodeAt ( 0 ) - 48 ; } // This function receives the String representation // of the number and precomputes the sum array function preCompute ( x ) { // Initialize everb sum [ 0 ]. e_sum = sum [ 0 ]. o_sum = 0 ; // Add the respective digits depending on whether // they're even indexed or odd indexed for ( let i = 0 ; i < x . length ; i ++ ) { if ( i % 2 == 0 ) { sum [ i + 1 ]. e_sum = sum [ i ]. e_sum + parseInt ( x [ i ]); sum [ i + 1 ]. o_sum = sum [ i ]. o_sum ; } else { sum [ i + 1 ]. o_sum = sum [ i ]. o_sum + parseInt ( x [ i ]); sum [ i + 1 ]. e_sum = sum [ i ]. e_sum ; } } } // This function receives l and r representing // the indices and prints the required output function query ( l r ) { let diff = ( sum [ r + 1 ]. e_sum - sum [ r + 1 ]. o_sum ) - ( sum [ l ]. e_sum - sum [ l ]. o_sum ); return ( diff % 11 == 0 ); } // driver function to check the program for ( let i = 0 ; i < MAX ; i ++ ) { sum [ i ] = new OddEvenSums (); } let s = '122164154695' ; preCompute ( s ); document . write (( query ( 0 3 ) ? 1 : 0 ) + '
' ); document . write (( query ( 1 2 ) ? 1 : 0 ) + '
' ); document . write (( query ( 5 9 ) ? 1 : 0 ) + '
' ); document . write (( query ( 0 11 ) ? 1 : 0 ) + '
' ); // This code is contributed by unknown2108 < /script>
Sortir:
1 1 0 1
