Biorąc pod uwagę dużą liczbę n (o cyfrach do 10^6) i różne zapytania w postaci:
Query(l r): sprawdza, czy podciąg pomiędzy indeksami l i r (oba włącznie) jest podzielny przez 3.
Przykłady:
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.
Wiemy, że każda liczba jest podzielna przez 3, jeśli suma jej cyfr jest podzielna przez 3. Dlatego pomysł polega na wstępnym przetworzeniu tablicy pomocniczej, która będzie przechowywać sumę cyfr.
nasiona vs zarodniki
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
Po przetworzeniu naszej tablicy pomocniczej możemy odpowiedzieć na każde zapytanie w czasie O(1), ponieważ podciąg od indeksów l do r byłby podzielny przez 3 tylko wtedy, gdy (suma[r+1]-sum[l])%3 == 0
Poniżej znajduje się program wdrożenia tego samego.
// 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 ?> Wyjście:
ciąg do rozmowy
Divisible by 3 Divisible by 3 Not divisible by 3 Divisible by 3
Złożoność czasu : NA)
Przestrzeń pomocnicza : NA)