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:
- Generate an array X of 10^7 tuples – (0,0).
- 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 - 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