Sub-string Divisibility by 11 Queries

0 0 6 minutes read

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.

Examples:

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:
In the first query, 1221 is divisible by 11
In the second query, 22 is divisible by 11 and so on.

We know that any number is divisible by 11 if the difference between the 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.
Hence, the idea is to pre-process an auxiliary array that would store the sum of digits at odd and even places.
To evaluate a query we can use the auxiliary array to answer it in 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

Javascript

<script>
// Javascript program to check divisibility by 11 in
// subStrings of a number String
let MAX = 1000005;
 
// To store sums of even and odd digits
class OddEvenSums
{
    constructor()
    {
        this.e_sum = 0;
        this.o_sum = 0;
         
    }
}
 
// Auxiliary array
let sum = new Array(MAX);
 
// Utility function to evaluate a character's
// integer value
function toInt(x)
{
    return x.charCodeAt(0) -     48;
}
 
// This function receives the String representation
// of the number and precomputes the sum array
function 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 (let i = 0; i < x.length; i++)
    {
        if (i % 2 == 0)
        {
            sum[i + 1].e_sum = sum[i].e_sum + parseInt(x[i]);
            sum[i + 1].o_sum = sum[i].o_sum;
        }
        else
        {
            sum[i + 1].o_sum = sum[i].o_sum + parseInt(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
function query(l,r)
{
    let 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
for (let i = 0; i < MAX; i++) {
    sum[i] = new OddEvenSums();
}
let s = "122164154695";
 
preCompute(s);
 
document.write((query(0, 3) ? 1 : 0)+"<br>");
document.write((query(1, 2) ? 1 : 0)+"<br>");
document.write((query(5, 9) ? 1 : 0)+"<br>");
document.write((query(0, 11) ? 1 :0)+"<br>");
 
// This code is contributed by unknown2108
</script>

Output:

This article is contributed by Ashutosh Kumar. If you like zambiatek and would like to contribute, you can also write an article using write.zambiatek.com or mail your article to review-team@zambiatek.com. See your article appearing on the zambiatek main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!