Given a large number, n (having number digits up to 10^6) and various queries of the form :
Query(l, r) : find if the sub-string between the indices l and r (Both inclusive) are divisible by 3.
Examples:
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 know that any number is divisible by 3 if the sum of its digits is divisible by 3. Hence the idea is to pre-process an auxiliary array that would store the sum of digits.
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
Once our auxiliary array is processed, we can answer each query in O(1) time, because the substring from indices l to r would be divisible by 3 only if, (sum[r+1]-sum[l])%3 == 0
Below is a the implementation program for the same.
C++
// C++ program to answer multiple queries of// divisibility by 3 in substrings of a number#include <iostream>using namespace std;// Array to store the sum of digitsint sum[1000005];// Utility function to evaluate a character's// integer valueint toInt(char x){ return int(x) - '0';}// This function receives the string representation// of the number and precomputes the sum arrayvoid 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 outputvoid query(int l,int r){ if ((sum[r+1]-sum[l])%3 == 0) cout << "Divisible by 3\n"; else cout << "Not divisible by 3\n";}// Driver function to check the programint main(){ string n = "12468236544"; prepareSum(n); query(0, 1); query(1, 2); query(3, 6); query(0, 10); return 0;} |
Java
// Java program to answer multiple queries of// divisibility by 3 in substrings of a numberclass 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
# Python3 program to answer multiple queries of# divisibility by 3 in substrings of a number# Array to store the sum of digitssum = [0 for i in range(1000005)]# Utility function to evaluate a character's# integer valuedef toInt(x): return int(x)# This function receives the string representation# of the number and precomputes the sum arraydef 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 outputdef 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 programif __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#
// C# program to answer multiple queries of// divisibility by 3 in substrings of a numberusing 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 */ |
Javascript
<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" + "<br />"); } else { document.write("Not divisible by 3" + "<br />"); } }// Driver Code let n = "12468236544"; prepareSum(n); query(0, 1); query(1, 2); query(3, 6); query(0, 10); </script> |
PHP
<?php // 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?> |
Output:
Divisible by 3 Divisible by 3 Not divisible by 3 Divisible by 3
Time Complexity: O(n)
Auxiliary Space: O(n)
If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
