算法题：计算字符串的子字符串的数字是否能被11整除

2021年3月31日18:19:13 发表评论 930 次浏览

本文概述

给定一个大数n(数字位数最多为10^6)和以下形式的各种查询：

Query(l, r) : 找出索引l和r(包括)之间的子字符串是否能被11整除。

例子： 

Input: n = 122164154695
Queries: l = 0 r = 3, l = 1 r = 2, l = 5 r = 9, l = 0 r = 11
Output:
True
False
False
True

Explanation:
在第一个查询中，1221能被11整除
在第二个查询中，22可以被11整除，以此类推。

我们知道, 如果将奇数索引的数字之和与偶数索引的数字之和之差除以11, 即总和(奇数位的数字)–总和(奇数位的数字)应被11整除。

因此，我们的想法是预处理一个辅助数组，该数组将存储奇数和偶数位的数字和。

要计算一个查询，我们可以使用辅助数组在O(1)中解决它。

C ++

// C++ program to check divisibility by 11 in
// substrings of a number string
#include <iostream>
using namespace std;
 
const int MAX = 1000005;
 
// To store sums of even and odd digits
struct OddEvenSums
{
     // Sum of even placed digits
     int e_sum;
 
     // Sum of odd placed digits
     int o_sum;
};
 
// Auxiliary array
OddEvenSums sum[MAX];
 
// Utility function to evaluate a character's
// integer value
int toInt( char x)
{
     return int (x) - 48;
}
 
// This function receives the string representation
// of the number and precomputes the sum array
void preCompute(string x)
{
     // Initialize everb
     sum[0].e_sum = sum[0].o_sum = 0;
 
     // Add the respective digits depending on whether
     // they're even indexed or odd indexed
     for ( int i=0; i<x.length(); i++)
     {
         if (i%2==0)
         {
             sum[i+1].e_sum = sum[i].e_sum+toInt(x[i]);
             sum[i+1].o_sum = sum[i].o_sum;
         }
         else
         {
             sum[i+1].o_sum = sum[i].o_sum+toInt(x[i]);
             sum[i+1].e_sum = sum[i].e_sum;
         }
     }
}
 
// This function receives l and r representing
// the indices and prints the required output
bool query( int l, int r)
{
     int diff = (sum[r+1].e_sum - sum[r+1].o_sum) -
                (sum[l].e_sum - sum[l].o_sum);
 
     return (diff%11==0);
}
 
//driver function to check the program
int main()
{
     string s = "122164154695" ;
 
     preCompute(s);
 
     cout << query(0, 3) << endl;
     cout << query(1, 2) << endl;
     cout << query(5, 9) << endl;
     cout << query(0, 11) << endl;
 
     return 0;
}

Java

// Java program to check divisibility by 11 in
// subStrings of a number String
class GFG
{
  
static int MAX = 1000005 ;
  
// To store sums of even and odd digits
static class OddEvenSums
{
     // Sum of even placed digits
     int e_sum;
  
     // Sum of odd placed digits
     int o_sum;
};
  
// Auxiliary array
static OddEvenSums []sum = new OddEvenSums[MAX];
  
// Utility function to evaluate a character's
// integer value
static int toInt( char x)
{
     return x - 48 ;
}
  
// This function receives the String representation
// of the number and precomputes the sum array
static void preCompute(String x)
{
     // Initialize everb
     sum[ 0 ].e_sum = sum[ 0 ].o_sum = 0 ;
  
     // Add the respective digits depending on whether
     // they're even indexed or odd indexed
     for ( int i = 0 ; i < x.length(); i++)
     {
         if (i % 2 == 0 )
         {
             sum[i + 1 ].e_sum = sum[i].e_sum + toInt(x.charAt(i));
             sum[i + 1 ].o_sum = sum[i].o_sum;
         }
         else
         {
             sum[i + 1 ].o_sum = sum[i].o_sum + toInt(x.charAt(i));
             sum[i + 1 ].e_sum = sum[i].e_sum;
         }
     }
}
  
// This function receives l and r representing
// the indices and prints the required output
static boolean query( int l, int r)
{
     int diff = (sum[r + 1 ].e_sum - sum[r + 1 ].o_sum) -
                (sum[l].e_sum - sum[l].o_sum);
  
     return (diff % 11 == 0 );
}
  
//driver function to check the program
public static void main(String[] args)
{
     for ( int i = 0 ; i < MAX; i++) {
         sum[i] = new OddEvenSums();
     }
     String s = "122164154695" ;
  
     preCompute(s);
  
     System.out.println(query( 0 , 3 ) ? 1 : 0 );
     System.out.println(query( 1 , 2 ) ? 1 : 0 );
     System.out.println(query( 5 , 9 ) ? 1 : 0 );
     System.out.println(query( 0 , 11 ) ? 1 : 0 );
  
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 program to check divisibility by
# 11 in subStrings of a number String
MAX = 1000005
 
# To store sums of even and odd digits
class OddEvenSums:
     
     def __init__( self , e_sum, o_sum):
         
         # Sum of even placed digits
         self .e_sum = e_sum
   
         # Sum of odd placed digits
         self .o_sum = o_sum
 
sum = [OddEvenSums( 0 , 0 ) for i in range ( MAX )]
 
# This function receives the String
# representation of the number and
# precomputes the sum array
def preCompute(x):
 
     # Initialize everb
     sum [ 0 ].e_sum = sum [ 0 ].o_sum = 0
   
     # Add the respective digits
     # depending on whether
     # they're even indexed or
     # odd indexed
     for i in range ( len (x)):
         if (i % 2 = = 0 ):
             sum [i + 1 ].e_sum = ( sum [i].e_sum +
                               int (x[i]))
             sum [i + 1 ].o_sum = sum [i].o_sum
         
         else :
             sum [i + 1 ].o_sum = ( sum [i].o_sum +
                               int (x[i]))
             sum [i + 1 ].e_sum = sum [i].e_sum
         
# This function receives l and r representing
# the indices and prints the required output
def query(l, r):
 
     diff = (( sum [r + 1 ].e_sum -
              sum [r + 1 ].o_sum) -
             ( sum [l].e_sum -
              sum [l].o_sum))
   
     if (diff % 11 = = 0 ):
         return True
     else :
         return False
 
# Driver code
if __name__ = = "__main__" :
     
     s = "122164154695"
   
     preCompute(s)
   
     print ( 1 if query( 0 , 3 ) else 0 )
     print ( 1 if query( 1 , 2 ) else 0 )
     print ( 1 if query( 5 , 9 ) else 0 )
     print ( 1 if query( 0 , 11 ) else 0 )
 
# This code is contributed by rutvik_56

C#

// C# program to check
// divisibility by 11 in
// subStrings of a number String
using System;
class GFG{
  
static int MAX = 1000005;
  
// To store sums of even
// and odd digits 
public class OddEvenSums
{
   // Sum of even placed digits
   public int e_sum;
 
   // Sum of odd placed digits
   public int o_sum;
};
  
// Auxiliary array
static OddEvenSums []sum =
        new OddEvenSums[MAX];
  
// Utility function to
// evaluate a character's
// integer value
static int toInt( char x)
{
   return x - 48;
}
  
// This function receives the
// String representation of the
// number and precomputes the sum array
static void preCompute(String x)
{
   // Initialize everb
   sum[0].e_sum = sum[0].o_sum = 0;
 
   // Add the respective digits
   // depending on whether they're
   // even indexed or odd indexed
   for ( int i = 0; i < x.Length; i++)
   {
     if (i % 2 == 0)
     {
       sum[i + 1].e_sum = sum[i].e_sum +
                          toInt(x[i]);
       sum[i + 1].o_sum = sum[i].o_sum;
     }
     else
     {
       sum[i + 1].o_sum = sum[i].o_sum +
                          toInt(x[i]);
       sum[i + 1].e_sum = sum[i].e_sum;
     }
   }
}
  
// This function receives l and r
// representing the indices and
// prints the required output
static bool query( int l, int r)
{
   int diff = (sum[r + 1].e_sum -
               sum[r + 1].o_sum) -
              (sum[l].e_sum -
               sum[l].o_sum);
 
   return (diff % 11 == 0);
}
  
// Driver function to check the program
public static void Main(String[] args)
{
   for ( int i = 0; i < MAX; i++)
   {
     sum[i] = new OddEvenSums();
   }
   
   String s = "122164154695" ;
   preCompute(s);
 
   Console.WriteLine(query(0, 3) ? 1 : 0);
   Console.WriteLine(query(1, 2) ? 1 : 0);
   Console.WriteLine(query(5, 9) ? 1 : 0);
   Console.WriteLine(query(0, 11) ? 1 : 0);
}
}
 
// This code is contributed by gauravrajput1

输出如下： 

1
1
0
1
木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: