Anmol Mahatpurkar - 6 months ago 97

Java Question

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.

- A big number of
digits,*N* - The number of questions
to be asked.*Q*

In each of the question, you have to find if the number formed by the string between indices

First line contains the number consisting on

For each question, print "YES" or "NO", if the number formed by the string between indices

1 ≤ N ≤ 10

1 ≤ Q ≤ 10

1 ≤ L

357753

3

1 2

2 3

4 4

YES

NO

YES

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

Now according to the constraints, the maximum length of the number i.e.

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.

`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

Therefore, the time taken to solve the problem becomes

After that didn't work, I tried searching for a

I did find one algorithm named

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

Answer

There are two ways to go through this problem.

**1: Dynamic Programming Approach**

Let the input be array of digits `A[N]`

.

Let `N[L,R]`

be number formed by digits `L to R`

.

Let another array be `M[N]`

where `M[i] = N[1,i] mod 7`

.

So `M[i+1] = ((M[i] * 10) mod 7 + A[i+1] mod 7) mod 7`

Pre-calculate array `M`

.

Now consider the expression.

`N[1,R] = N[1,L-1] *`

10^{R-L+1} `+ N[L,R]`

`implies (N[1,R] mod 7) = (N[1,L-1] mod 7 *`

(10^{R-L+1}`mod 7)) + (N[L,R] mod 7)`

`implies N[L,R] mod 7 = (M[R] - M[L-1] *`

(10^{R-L+1} `mod 7)) mod 7`

`N[L,R] mod 7`

gives your answer and can be calculated in `O(1)`

as all values on right of expression are already there.
For 10^{R-L+1} `mod 7`

, you can pre-calculate modulo 7 for all powers of 10.

Time Complexity :

Precalculation `O(N)`

Overall `O(Q) + O(N)`

**2: Divide and Conquer Approach**

Its a segment tree solution.
On each tree node you store the mod 7 for the number formed by digits in that node.

And the expression given in first approach can be used to find the mod 7 of parent by combining the mod 7 values of two children.

The time complexity of this solution will be `O(Q log N) + O(N log N)`