3개 쿼리로 하위 문자열 분할 가능
큰 숫자 n(최대 10^6의 숫자 포함)과 다음 형식의 다양한 쿼리가 제공됩니다.
쿼리(l r) : 인덱스 l과 r(둘 다 포함) 사이의 하위 문자열이 3으로 나누어지는지 확인합니다.
예:
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.
숫자의 합이 3으로 나누어지면 모든 숫자는 3으로 나누어진다는 것을 알고 있습니다. 따라서 숫자의 합을 저장하는 보조 배열을 전처리하는 것이 아이디어입니다.
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
보조 배열이 처리되면 O(1) 시간 내에 각 쿼리에 응답할 수 있습니다. 왜냐하면 인덱스 l에서 r까지의 하위 문자열은 (sum[r+1]-sum[l])%3 == 0인 경우에만 3으로 나눌 수 있기 때문입니다.
아래는 이에 대한 구현 프로그램입니다.
// 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 ?>
산출:
Divisible by 3 Divisible by 3 Not divisible by 3 Divisible by 3
시간 복잡도 : 에)
보조 공간 : 에)
