子字符串被3个查询整除-yiteyi-C++库

给定一个大数字，n（数字位数最多为10^6）和各种形式的查询：查询（l，r）：查找索引l和r（均包含）之间的子字符串是否可被3整除。例如：

null

Input: n = 12468236544Queries:l=0 r=1l=1 r=2l=3 r=6l=0 r=10Output:Divisible by 3 Divisible by 3 Not divisible by 3Divisible by 3Explanation:In the first query, 12 is divisible by 3In the second query, 24 is divisible by 3 and so on.

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

我们知道任何数字都可以被3整除，如果其数字之和可以被3整除。因此，我们的想法是预处理一个辅助数组，该数组将存储数字之和。

Mathematically,sum[0] = 0and 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

一旦我们的辅助数组被处理，我们就可以在O（1）时间内回答每个查询，因为从索引l到r的子串只有在（sum[r+1]-sum[l]）%3==0时才可以被3整除下面是一个同样的实施方案。

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 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<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                       
                         void                                     query(                                     int                                     l,                                     int                                     r)                       
                         {                       
                                                 if                                     ((sum[r+1]-sum[l])%3 == 0)                       
                                                 cout <<                                     "Divisible by 3"                                     ;                       
                                                 else                       
                                                 cout <<                                     "Not divisible by 3"                                     ;                       
                         }                       
           
                         // Driver function to check the program                       
                         int                                     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 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

                         <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>                       

输出：

Divisible by 3Divisible by 3Not divisible by 3Divisible by 3

本文由 阿什图什·库马尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章