Étant donné un grand nombre n (ayant des chiffres jusqu'à 10 ^ 6) et diverses requêtes de la forme :
Requête(l r) : recherche si la sous-chaîne entre les indices l et r (tous deux inclus) est divisible par 3.
Exemples :
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.
Nous savons que tout nombre est divisible par 3 si la somme de ses chiffres est divisible par 3. L'idée est donc de prétraiter un tableau auxiliaire qui stockerait la somme des chiffres.
comment vérifier les numéros bloqués sur Android
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
Une fois notre tableau auxiliaire traité, nous pouvons répondre à chaque requête en un temps O(1) car la sous-chaîne des indices l à r ne serait divisible par 3 que si (sum[r+1]-sum[l])%3 == 0
Vous trouverez ci-dessous le programme de mise en œuvre de celui-ci.
// 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 ?> Sortir:
programme java simple
Divisible by 3 Divisible by 3 Not divisible by 3 Divisible by 3
Complexité temporelle : Sur)
Espace auxiliaire : Sur)