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

so question on 1 of challenges came across in online competition, few days ago.

question:

accept 2 inputs.

1. a big number of n digits,
2. the number of questions q asked.

in each of question, have find if number formed string between indices l_i , r_i divisible 7 or not.

input:

first line contains number consisting on n digits. next line contains q, denoting number of questions. each of next q lines contains 2 integers l_i , r_i.

output:

for each question, print "yes" or "no", if number formed string between indices l_i , r_i divisible 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 first query, number 35 divisible 7.

---

time limit: 1.0 sec each input file.

memory limit: 256 mb

source limit: 1024 kb

---

my approach:

now according constraints, maximum length of number i.e. n can upto 10⁵. big number cannot fitted numeric data structure , pretty sure thats not efficient way go it.

first try:

i thought of algorithm apply generic rules of division each individual digit of number. work check divisibility amongst 2 numbers, in linear time, i.e. o(n).

static string isdivisibleby(string theindexednumber, int divisiblityno){      int modulovalue = 0;      for(int = 0; < theindexednumber.length(); i++){          modulovalue = modulovalue * 10;         modulovalue += character.getnumericvalue(theindexednumber.charat(i));         modulovalue %= divisiblityno;     }      if(modulovalue == 0){         return "yes";     } else{         return "no";     }  } 

but in case, algorithm has loop through values of q, can upto 10⁵.

therefore, time taken solve problem becomes o(q.n) can considered quadratic time. hence, crossed given time limit , not efficient.

second try:

after didn't work, tried searching divisibility rule of 7. ones found, involved calculations based on each individual digit of number. hence, again result in linear time algorithm. , hence, combined number of questions, amount quadratic time, i.e. o(q.n)

i did find 1 algorithm named pohlman–mass method of divisibility 7, suggested

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

but did was, make time 1/3rd q.n, didn't much.

---

am missing here? can me find way solve efficiently?

also, there chance dynamic programming problem?

there 2 ways go through problem.

1: dynamic programming approach
let input array of digits a[n].
let n[l,r] number formed digits l r.
let array m[n] m[i] = n[1,i] mod 7.
m[i+1] = ((m[i] * 10) mod 7 + a[i+1] mod 7) mod 7
pre-calculate array m.

now consider 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+1mod 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 answer , can calculated in o(1) values on right of expression there. 10^r-l+1 mod 7, can pre-calculate modulo 7 powers of 10.

time complexity :
precalculation o(n)
overall o(q) + o(n)

2: divide , conquer approach
segment tree solution. on each tree node store mod 7 number formed digits in node.
, expression given in first approach can used find mod 7 of parent combining mod 7 values of 2 children.
time complexity of solution o(q log n) + o(n log n)