Duotas didelis skaičius n (turintis skaičių skaitmenis iki 10^6) ir įvairios formos užklausos:
Užklausa(l r) : suraskite, ar poeilutė tarp indeksų l ir r (Abu imtinai) dalijasi iš 3.
Pavyzdžiai:
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.
Žinome, kad bet kuris skaičius dalijasi iš 3, jei jo skaitmenų suma dalijasi iš 3. Taigi idėja yra iš anksto apdoroti pagalbinį masyvą, kuriame būtų saugoma skaitmenų suma.
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
Apdorojus mūsų pagalbinį masyvą, galime atsakyti į kiekvieną užklausą per O(1) laiką, nes poeilutė nuo indeksų l iki r būtų dalijama iš 3 tik tuo atveju, jei (sum[r+1]-sum[l])%3 == 0
Žemiau pateikiama to paties įgyvendinimo programa.
// 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 ?> Išvestis:
Divisible by 3 Divisible by 3 Not divisible by 3 Divisible by 3
Laiko sudėtingumas : O(n)
Pagalbinė erdvė : O(n)