Sub-string Divisibility by 11 Queries - GeeksforGeeks
Given a large number, n (having number digits up to 10^6) and various queries of the below form :
Read full article from Sub-string Divisibility by 11 Queries - GeeksforGeeks
Given a large number, n (having number digits up to 10^6) and various queries of the below form :
Query(l, r) : find if the sub-string between the indices l and r (Both inclusive) are divisible by 11.
We know that any number is divisible by 11 if the difference between sum of odd indexed digits and the sum of even indexed digits is divisible by 11, i.e.,
Sum(digits at odd places) – Sum(digits at even places) should be divisible by 11.
Sum(digits at odd places) – Sum(digits at even places) should be divisible by 11.
Hence the idea is to pre-process an auxiliary array that would store sum of digits at odd and even places.
To evaluate a query we can use the auxiliary array to answer it in O(1).
To evaluate a query we can use the auxiliary array to answer it in O(1).
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);
}