text: # Sub-string Divisibility by 3 Queries
  
  • Difficulty Level : Easy
  • Last Updated : 21 Jul, 2022
  
  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 ``using` `namespace` `std;` `// Array to store the sum of digits``int` `sum[1000005];` `// Utility function to evaluate a character's``// integer value``int` `toInt(``char` `x)``{``    ``return` `int``(x) - ``'0'``;``}` `// This function receives the string representation``// of the number and precomputes the sum array``void` `prepareSum(string s)``{``    ``sum[0] = 0;``    ``for` `(``int` `i=0; i
  
  ## Java
  
   `// 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
  
   `# 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#
  
   `// 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 */`
  
  ## Javascript
  
   ``
  
  ## PHP
  
   ``
  
  Output:
  
  ```Divisible by 3
  Divisible by 3
  Not divisible by 3
  Divisible by 3```
  
  Time Complexity: O(n)
  
  Auxiliary Space: O(n)
  This article is contributed by Ashutosh Kumar. If you like GeeksforGeeks 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 GeeksforGeeks main page and help other Geeks.