Minimize array and output the remainder with respect to 1 second time limit

Question

This is my code:

n = int(raw_input())
seq = raw_input().split()
def minimize_list(lst):
    new_lst = []
    k = len(lst)
    for i in range(k-1):
        new_lst.append(lst[i+1]-lst[i])
    return new_lst
for i in range(len(seq)):
    seq[i] = int(seq[i])
final_list = []
for num in seq:
    final_list.append(num)
while len(final_list) != 1:
    final_list = minimize_list(final_list)
print (final_list[0])%(1000000000+7)

It takes a number and a sequence of numbers. (The first number is the number of numbers in the sequence). It then calculates a shorter sequence with the difference of adjacent numbers until there is just 1 number. Unfortunately, The time complexity is not good enough. I have to make it better to meet the time limit which is 1 second.

Any idea?

Note: I cannot see the input. I can just pass my code to a server which has 10 examples and runs my code on them. The server then tells me that this code has exceeded the time limit for some examples.

Update: I want to print (final_list[0])%(1000000000+7)

Answer 1

One easy way is to use numpy, which is implemented in C (if it is available on the machine your online judge is running on). It provides fast ways to do numerical calculations. In this case, you can use numpy.diff, which calculates the difference between elements. It even has a n argument, so it applies it n times. We also know how often we need to apply it to get only a single element, len(seq) - 1 times:

import numpy as np

n = int(raw_input())
seq = map(int, raw_input().split())
print np.diff(seq, len(seq) -1)[0]

---

If you need to stick to built-in methods, you could at least make the minimize_list method a bit shorter using a list comprehension (and maybe rename it to diff):

def diff(x):
    return [b - a for a, b in zip(x, x[1:])]

def reduce_diff(seq):
    while len(seq) > 1:
        seq = diff(seq)
    return seq[0]

if __name__ == "__main__":
    n = int(raw_input())
    seq = map(int, raw_input().split())
    print reduce_diff(seq)

I also removed the redundant copying from seq to final_list and instead of the for loop to convert all values to integers I used map.

Be aware that if you want to use this with Python 3 (as you should, since Python 2 will be obsolete soon), you need to surround that map call with a call to list and replace raw_input with input.

In addition I added a if __name__ == "__main__": guard to allow importing from this script from another script.

---

And finally, one can notice that this approach is \$\mathcal{O}(n^2)\$. When looking at a simple example of successive application of diff, a pattern becomes obvious:

\$ a, b, c, d, e\\ b-a, c-b, d-c, e-d\\ c-2b+a,d-2c+b, e-2d+c\\ d-3c+3b-a, e-3d+3c-b\\ e-4d+6c-4b+a \$

The coefficients are the ones from Pascals triangle, together with an alternating sign:

\$ \begin{pmatrix} & & & & 1 & & & &\\ & & & 1 & & 1 & & & \\ & & 1 & & 2 & & 1 & & \\ & 1 & & 3 & & 3 & & 1 & \\ 1 & & 4 & & 6 & & 4 & & 1 \end{pmatrix} \$

So, if you find a fast way to calculate the n-th row of Pascal's triangle, you can solve this problem in \$\mathcal{O}(n)\$, by adding the terms with a plus, modulo p and the ones with a minus, modulo p and then subtract them:

from itertools import cycle

def pascal_line(n):
    line = [1]
    mid, even = divmod(n, 2)
    line_append = line.append
    for k in xrange(1, mid + 1):
        num = line[k-1]*(n + 1 - k)//(k)
        line_append(num)
    reverse_it = reversed(line)
    if not even:
        next(reverse_it)
    line.extend(reverse_it)
    return line

def reduce_pascal(seq):
    return sum(sign * c * x
               for sign, c, x in zip(cycle([1, -1]),
                                     pascal_line(len(seq)-1),
                                     reversed(seq)))

if __name__ == "__main__":
    n = int(raw_input())
    seq = map(int, raw_input().split())
    p = 1000000000+7
    print reduce_pascal(seq) % p

One could make this also modular p at each step by doing the sum manually and enforcing the mod p.

Beware: This seems to break down for large sequences (since the terms in the triangle get big).