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.
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";
}
}
Using quick alternating additions and subtractions:
42,341,530
-> 530 − 341 = 189 + 42 = 231 -> 23 − (1×2) = 21 YES
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)