Effiecient Algorithm for Finding if a Very Big Number is Divisible by 7

So this was a question on one of the challenges I came across in an online competition, a few days ago.

Question:

Accept two inputs.

1. A big number of N digits,


2. The number of questions Q to be asked.

In each of the question, you have to find if the number formed by the string between indices L_i and R_i is divisible by 7 or not.

Input:

First line contains the number consisting on N digits. Next line contains Q, denoting the number of questions. Each of the next Q lines contains 2 integers L_i and R_i.

Output:

For each question, print "YES" or "NO", if the number formed by the string between indices L_i and R_i is divisible by 7.

Constraints:

1 ≤ N ≤ 10⁵

1 ≤ Q ≤ 10⁵

1 ≤ L_i, R_i ≤ N

Sample Input:

357753

3

1 2

2 3

4 4


Sample Output:

YES

NO

YES


Explanation:

For the first query, number will be 35 which is clearly divisible by 7.

---

Time Limit: 1.0 sec for each input file.

Memory Limit: 256 MB

Source Limit: 1024 KB

---

My Approach:

Now according to the constraints, the maximum length of the number i.e. N can be upto 10⁵. This big a number cannot be fitted into a numeric data structure and I am pretty sure thats not the efficient way to go about it.

First Try:

I thought of this algorithm to apply the generic rules of division to each individual digit of the number. This would work to check divisibility amongst any two numbers, in linear time, i.e. O(N).

static String isDivisibleBy(String theIndexedNumber, int divisiblityNo){



    int moduloValue = 0;



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



        moduloValue = moduloValue * 10;

        moduloValue += Character.getNumericValue(theIndexedNumber.charAt(i));

        moduloValue %= divisiblityNo;

    }



    if(moduloValue == 0){

        return "YES";

    } else{

        return "NO";

    }



}

But in this case, the algorithm has to also loop through all the values of Q, which can also be upto 10⁵.

Therefore, the time taken to solve the problem becomes O(Q.N) which can also be considered as Quadratic time. Hence, this crossed the given time limit and was not efficient.

Second Try:

After that didn't work, I tried searching for a divisibility rule of 7. All the ones I found, involved calculations based on each individual digit of the number. Hence, that would again result in a Linear time algorithm. And hence, combined with the number of Questions, it would amount to Quadratic Time, i.e. O(Q.N)

I did find one algorithm named Pohlman–Mass method of divisibility by 7, which suggested

Using quick alternating additions and subtractions:
42,341,530
-> 530 − 341 = 189 + 42 = 231 -> 23 − (1×2) = 21 YES

But all that did was, make the time 1/3rd Q.N, which didn't help much.

---

Am I missing something here? Can anyone help me find a way to solve this efficiently?

Also, is there a chance this is a Dynamic Programming problem?