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.
- A big number of N digits,
- 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 Li and Ri 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 Li and Ri.
Output:
For each question, print "YES" or "NO", if the number formed by the string between indices Li and Ri is divisible by 7.
Constraints:
1 ≤ N ≤ 105
1 ≤ Q ≤ 105
1 ≤ Li, Ri ≤ 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 105. 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 105.
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?
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] * 10R-L+1 + N[L,R]
implies (N[1,R] mod 7) = (N[1,L-1] mod 7 * (10R-L+1mod 7)) + (N[L,R] mod 7)
implies N[L,R] mod 7 = (M[R] - M[L-1] * (10R-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 10R-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)