큰 숫자 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
// 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 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# 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 */
<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 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
시간 복잡도 : 에)
보조 공간 : 에)