Dělitelnost podřetězců 3 dotazy
Vzhledem k velkému počtu n (s číslicemi do 10^6) a různým dotazům ve tvaru:
Query(l r) : zjistěte, zda je podřetězec mezi indexy l a r (oba včetně) dělitelný 3.
Příklady:
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.
Víme, že každé číslo je dělitelné 3, pokud je součet jeho cifer dělitelný 3. Myšlenka je tedy předem zpracovat pomocné pole, které by uložilo součet cifer.
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
Jakmile je naše pomocné pole zpracováno, můžeme odpovědět na každý dotaz v čase O(1), protože podřetězec od indexů l do r by byl dělitelný 3 pouze v případě, že (sum[r+1]-součet[l])%3 == 0
Níže je uveden implementační program pro totéž.
// 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 ?>
výstup:
Divisible by 3 Divisible by 3 Not divisible by 3 Divisible by 3
Časová složitost : O(n)
Pomocný prostor : O(n)
