Finding all substrings of a given number that are divisible by 11



Finding all substrings of a given number that are divisible by 11

To find easy to way of Divisibility by 11,

  • The multiples of 11: 22, 33, 44, 55, etc. But we did't easy to find the number 2728, 54695 is divisible by 11.
  • Here an easy way to test for divisibility by 11. Take the alternating sum of the digits in the number, read from left to right. If that is divisible by 11, so is the original number.
  • So, for example, 2728 has alternating sum of digits 2-7+2-8 = -11. Since -11 is divisible by 11, so is 2728.
  • Similarly, for 54695, the alternating sum of digits is 5-4+6-9+5 = 3. This is not divisible by 11, so neither is 54695.

Read Also

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.

Input

n = 122164154695
Queries: l = 0 r = 3, l = 1 r = 2, l = 5 r = 9, l = 0 r = 11

Output

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

    Sample code

    #include <iostream> 
    using namespace std; 
      
    const int MAX = 1000005; 
      
    // To store sums of even and odd digits 
    struct OddEvenSums 
    { 
        int e_sum; // Sum of even placed digits 
      
        int o_sum; // Sum of odd placed digits 
    }; 
      
    OddEvenSums sum[MAX]; // Auxiliary array 
      
    // 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) 
    {  
        sum[0].e_sum = sum[0].o_sum = 0; // Initialize everb 
      
        // 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; 
    } 

    Output

    1
    1
    0
    1
    


    Related Searches to Finding all substrings of a given number that are divisible by 11