Divisibilitat de subcadenes per 3 consultes
Donat un gran nombre n (que té dígits fins a 10^6) i diverses consultes de la forma:
Consulta (l r): troba si la subcadena entre els índexs l i r (tots dos inclosos) són divisibles per 3.
Exemples:
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.
Sabem que qualsevol nombre és divisible per 3 si la suma dels seus dígits és divisible per 3. Per tant, la idea és preprocessar una matriu auxiliar que emmagatzemi la suma de dígits.
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
Un cop processada la nostra matriu auxiliar, podem respondre cada consulta en el temps O(1) perquè la subcadena dels índexs l a r seria divisible per 3 només si (sum[r+1]-sum[l])%3 == 0
A continuació es mostra el programa d'implementació del mateix.
// 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 ?>
Sortida:
Divisible by 3 Divisible by 3 Not divisible by 3 Divisible by 3
Complexitat temporal : O(n)
Espai Auxiliar : O(n)
