This challenge describes the following algorithm:

Start with a list of 10^7 zeros and for every line containing a,b,c separated by a space in the given file, add c modulo 10 to every number in your list between indices a and b (a included only).
Indices start at 1 in the list. At the end, compute the product modulo 999999937 of the nonzero digits in your list and you will obtain the password

In addition, we get a file called “Given_file.txt” that cointains 10^7 lines as described in the algorithm description.
If we try to solve this just by following the algorithm description, we will end up with a complexity of O(n^2) where n is the number of lines, which is 10^7. This yields a very long running time, so we better think about some other way.

In order to solve this problem in linear complexity we can do the following:

1. Generate an array X of 10^7 tuples – (0,0).
2. Traverse the input file and update X as follows: x[a][0] = (x[a][0] + c)%10
   x[b][1] = (x[b][1] – c)%10
3. Compute the result by traversing X as follows:

   result = 1
   cur = 0
   for i in range(1, len(x)):
       cur = (cur + x[i][0] + x[i][1]) % 10
       if cur != 0:
           result = (result * cur) % 999999937