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

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

本文概述

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

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

# 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;
}

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

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