Sub-string Divisibility by 3 Queries - GeeksforGeeks

Sub-string Divisibility by 3 Queries - GeeksforGeeks
Given a large number, n (having number digits up to 10^6) and various queries of the form :
Query(l, r) : find if the sub-string between the indices l and r (Both inclusive) are divisible by 3.

We know that any number is divisible by 3 if the sum of its digits is divisible by 3. Hence the idea is to pre-process an auxiliary array that would store the sum of digits.

void prepareSum(string s)

{

    sum[0] = 0;

    for (int i=0; i<s.length(); i++)

        sum[i+1] = sum[i] + toInt(s[i]);

}

 

// This function receives l and r representing

// the indices and prints the required output

void query(int l,int r)

{

    if ((sum[r+1]-sum[l])%3 == 0)

        cout << "Divisible by 3\n";

    else

        cout << "Not divisible by 3\n";

}

Read full article from Sub-string Divisibility by 3 Queries - GeeksforGeeks