Gegeven een groot getal n (met cijfers tot 10^6) en verschillende zoekopdrachten van de vorm:
Query(l r) : zoek of de subtekenreeks tussen de indices l en r (beide inclusief) deelbaar is door 3.
Voorbeelden:
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.
We weten dat elk getal deelbaar is door 3 als de som van de cijfers deelbaar is door 3. Daarom is het idee om een hulparray vooraf te verwerken die de som van de cijfers zou opslaan.
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
Zodra onze hulparray is verwerkt, kunnen we elke vraag in O(1) tijd beantwoorden, omdat de substring van indices l tot r alleen deelbaar zou zijn door 3 als (sum[r+1]-sum[l])%3 == 0
Hieronder vindt u een implementatieprogramma hiervoor.
// 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 ?> Uitgang:
Divisible by 3 Divisible by 3 Not divisible by 3 Divisible by 3
Tijdcomplexiteit : Op)
Hulpruimte : Op)