Finding the last digit of partial sum of Fibonacci series

Question

def sum_fib(m, n):
    a = list()
    a.append(0)
    a.append(1)
    i = 2
    while i <= n:
        a.append((a[i - 1] + a[i - 2]) % 10)
        if a[i] == 1 and a[i - 1] == 0:
            break
        i += 1
    if n > 60:
        a.pop()
    # res = sum(a) % 10
    q = n - m
    j = m % 60
    su = 0
    
    while q >= 0:
        su += a[j]
        j += 1
        if j == 60:
            j = 0
        q -= 1

    return su % 10
        
    
num = [int(x) for x in raw_input().split()]
print sum_fib(num[0], num[1])

This code is giving the expected output, but it is taking too much time for large Fibonacci numbers. Please help me with this.

For input: 1 100000000

I'm getting:

time limit exceeded error. Time used: 9.36/5.00

Answer 1

You are trying to use the Fibonacci 60 Repeating Pattern, but not efficiently:

With the following loop you still collect potentially thousands of Fibonacci numbers, while you only need 60 of them:

while i <= n:
    a.append((a[i - 1] + a[i - 2]) % 10)

To avoid that you would have to run through those 60 numbers many times, you can use the property that the last digit of the sum of 60 consecutive Fibonacci numbers is always 0. This practically means you don't need to sum thousands of numbers, just a part of the first 60 Fibonacci numbers, since adding 60 more will not change the last digit of the sum.

So,... you could just trim the input variables by taking the modulo 60 of them, and then run through the stored list of 60 Fibonacci to calculate the needed sum.

Here is the adapted code:

def sum_fib(m, n):
    if m > n:
        return

    # Collect 60 Fibonnaci numbers
    a = [0, 1]
    for i in xrange(2, 60):
        a.append(a[i - 1] + a[i - 2])
    
    # Simplify the input arguments, as the last digit pattern repeats with a period of 60, 
    # and the sum of 60 such consecutive numbers is 0 mod 10:
    m = m % 60
    n = n % 60
    # Make sure n is greater than m
    if n < m: 
        n += 60

    su = 0
    for j in xrange(m, n + 1): # Assume n index is inclusive
        su += a[j % 60]

    return su % 10