Teilbarkeit von Teilzeichenfolgen durch 3 Abfragen
Gegeben sei eine große Zahl n (mit Ziffern bis zu 10^6) und verschiedene Abfragen der Form:
Query(l r) : Finden Sie heraus, ob die Teilzeichenfolge zwischen den Indizes l und r (beide einschließlich) durch 3 teilbar ist.
Beispiele:
Input: n = 12468236544 Queries: l=0 r=1 l=1 r=2 l=3 r=6 l=0 r=10 Output: Divisible by 3 Divisible by 3 Not divisible by 3 Divisible by 3 Explanation: In the first query 12 is divisible by 3 In the second query 24 is divisible by 3 and so on.
Wir wissen, dass jede Zahl durch 3 teilbar ist, wenn die Summe ihrer Ziffern durch 3 teilbar ist. Daher besteht die Idee darin, ein Hilfsarray vorzuverarbeiten, das die Summe der Ziffern speichert.
Mathematically sum[0] = 0 and for i from 0 to number of digits of number: sum[i+1] = sum[i]+ toInt(n[i]) where toInt(n[i]) represents the integer value of i'th digit of n
Sobald unser Hilfsarray verarbeitet ist, können wir jede Anfrage in O(1)-Zeit beantworten, da die Teilzeichenfolge der Indizes l bis r nur dann durch 3 teilbar wäre, wenn (sum[r+1]-sum[l])%3 == 0
Nachfolgend finden Sie das Implementierungsprogramm dafür.
// C++ program to answer multiple queries of // divisibility by 3 in substrings of a number #include using namespace std ; // Array to store the sum of digits int sum [ 1000005 ]; // Utility function to evaluate a character's // integer value int toInt ( char x ) { return int ( x ) - '0' ; } // This function receives the string representation // of the number and precomputes the sum array void prepareSum ( string s ) { sum [ 0 ] = 0 ; for ( int i = 0 ; i < s . length (); i ++ ) sum [ i + 1 ] = sum [ i ] + toInt ( s [ i ]); } // This function receives l and r representing // the indices and prints the required output void query ( int l int r ) { if (( sum [ r + 1 ] - sum [ l ]) % 3 == 0 ) cout < < 'Divisible by 3 n ' ; else cout < < 'Not divisible by 3 n ' ; } // Driver function to check the program int main () { string n = '12468236544' ; prepareSum ( n ); query ( 0 1 ); query ( 1 2 ); query ( 3 6 ); query ( 0 10 ); return 0 ; }
Java // Java program to answer multiple queries of // divisibility by 3 in substrings of a number class GFG { // Array to store the sum of digits static int sum [] = new int [ 1000005 ] ; // Utility function to evaluate a character's // integer value static int toInt ( char x ) { return x - '0' ; } // This function receives the string representation // of the number and precomputes the sum array static void prepareSum ( String s ) { sum [ 0 ] = 0 ; for ( int i = 0 ; i < s . length (); i ++ ) { sum [ i + 1 ] = sum [ i ] + toInt ( s . charAt ( i )); } } // This function receives l and r representing // the indices and prints the required output static void query ( int l int r ) { if (( sum [ r + 1 ] - sum [ l ] ) % 3 == 0 ) { System . out . println ( 'Divisible by 3' ); } else { System . out . println ( 'Not divisible by 3' ); } } // Driver code public static void main ( String [] args ) { String n = '12468236544' ; prepareSum ( n ); query ( 0 1 ); query ( 1 2 ); query ( 3 6 ); query ( 0 10 ); } } // This code has been contributed by 29AjayKumar
Python3 # Python3 program to answer multiple queries of # divisibility by 3 in substrings of a number # Array to store the sum of digits sum = [ 0 for i in range ( 1000005 )] # Utility function to evaluate a character's # integer value def toInt ( x ): return int ( x ) # This function receives the string representation # of the number and precomputes the sum array def prepareSum ( s ): sum [ 0 ] = 0 for i in range ( 0 len ( s )): sum [ i + 1 ] = sum [ i ] + toInt ( s [ i ]) # This function receives l and r representing # the indices and prints the required output def query ( l r ): if (( sum [ r + 1 ] - sum [ l ]) % 3 == 0 ): print ( 'Divisible by 3' ) else : print ( 'Not divisible by 3' ) # Driver function to check the program if __name__ == '__main__' : n = '12468236544' prepareSum ( n ) query ( 0 1 ) query ( 1 2 ) query ( 3 6 ) query ( 0 10 ) # This code is contributed by # Sanjit_Prasad
C# // C# program to answer multiple queries of // divisibility by 3 in substrings of a number using System ; class GFG { // Array to store the sum of digits static int [] sum = new int [ 1000005 ]; // Utility function to evaluate a character's // integer value static int toInt ( char x ) { return x - '0' ; } // This function receives the string representation // of the number and precomputes the sum array static void prepareSum ( String s ) { sum [ 0 ] = 0 ; for ( int i = 0 ; i < s . Length ; i ++ ) { sum [ i + 1 ] = sum [ i ] + toInt ( s [ i ]); } } // This function receives l and r representing // the indices and prints the required output static void query ( int l int r ) { if (( sum [ r + 1 ] - sum [ l ]) % 3 == 0 ) { Console . WriteLine ( 'Divisible by 3' ); } else { Console . WriteLine ( 'Not divisible by 3' ); } } // Driver code public static void Main () { String n = '12468236544' ; prepareSum ( n ); query ( 0 1 ); query ( 1 2 ); query ( 3 6 ); query ( 0 10 ); } } /* This code contributed by PrinciRaj1992 */
JavaScript < script > // JavaScript program to answer multiple queries of // divisibility by 3 in substrings of a number // Array to store the sum of digits let sum = []; // Utility function to evaluate a character's // integer value function toInt ( x ) { return x - '0' ; } // This function receives the string representation // of the number and precomputes the sum array function prepareSum ( s ) { sum [ 0 ] = 0 ; for ( let i = 0 ; i < s . length ; i ++ ) { sum [ i + 1 ] = sum [ i ] + toInt ( s [ i ]); } } // This function receives l and r representing // the indices and prints the required output function query ( l r ) { if (( sum [ r + 1 ] - sum [ l ]) % 3 == 0 ) { document . write ( 'Divisible by 3' + '
' ); } else { document . write ( 'Not divisible by 3' + '
' ); } } // Driver Code let n = '12468236544' ; prepareSum ( n ); query ( 0 1 ); query ( 1 2 ); query ( 3 6 ); query ( 0 10 ); < /script>
PHP // PHP program to answer multiple queries of // divisibility by 3 in substrings of a number // Array to store the sum of digits $sum = []; // Utility function to evaluate a character's // integer value function toInt ( $x ) { return $x - '0' ; } // This function receives the string representation // of the number and precomputes the sum array function prepareSum ( $s ) { $sum [ 0 ] = 0 ; for ( $i = 0 ; $i < strlen ( $s ); $i ++ ) { $sum [ $i + 1 ] = $sum [ $i ] + toInt ( $s [ $i ]); } } // This function receives l and r representing // the indices and prints the required output function query ( $l $r ) { if (( $sum [ $r + 1 ] - $sum [ $l ]) % 3 == 0 ) { echo ( 'Divisible by 3' ); } else { echo ( 'Not divisible by 3' ); } } // Driver Code $n = '12468236544' ; prepareSum ( $n ); query ( 0 1 ); query ( 1 2 ); query ( 3 6 ); query ( 0 10 ); // This code is contributed by laxmigangarajula03 ?>
Ausgabe:
Divisible by 3 Divisible by 3 Not divisible by 3 Divisible by 3
Zeitkomplexität : An)
Hilfsraum : An)
