 # ENCJMAY5 - Editorial

Author: Abhishek Kumar
Tester: Sandeep Singh,Arnab Chanda

EASY

# PREREQUISITES:

Fibonacci Sequence and little bit pisano period

# PROBLEM:

You are given L and R and have to calculate sum of last digit of each term in range [L,R] of fibonacci sequence.

# EXPLANATION:

For solving this problem efficiently we need to use dynamic programming.

Quick Hint Last digit of fibbonaci series repeats after 60th term (0 to 59). and follows [Pisano Period](https://www.geeksforgeeks.org/fibonacci-number-modulo-m-and-pisano-period/)
Hint

Last digit of fibonaci series repeats after 60th term (0 to 59).Therefore we can generate a list having fibonacci series from 0 to 59 (total 60 terms).and then we will iterate from L to R.If L to R is out of range from 0 to 59.Then we will try to use Dynamic Programming.

If L-R>=59 then we will calculate no of rounds like… rounds=(L-R)//60
We will precompute sum of last digit of each term from 0 to 59 once and then we will use whenever having more than 1 round.

# SOLUTION:

Setter's Solution
``````def gen(lists,l,r):
sums=0;diff=r-l
if(l%60==0):
round=diff//60
score=round*280
i=1
while(i<=r%60):
sums+=lists[i]
i+=1
val=sums+score
print(val)

elif(diff>=59):
val=l%60
diff=r-l
for p in range(val,60):
sums+=lists[p]
l=l-(l%60)+60
round=(r-l)//60
if(round>=0):
score=round*280
k=1
while(k<=r%60):
sums+=lists[k]
k+=1
val=score+sums;
print(val)

else:
if(r%60>=59):
j=l%60
while(j<=59):
sums+=lists[j]
j+=1
r-=59
m=r%60
for i in range(1,m+1):
sums+=lists[i]
print(sums)
else:
m=l%60
m2=r%60
for i in range(m,m2+1):
sums+=lists[i]
print(sums)
def fib(lists,l,r):
lists=0
lists=1
for i in range(2,60):
lists[i]=(lists[i-1]+lists[i-2])%10
gen(lists,l,r)

for i in range(int(input())):
l,r=map(int,input().split())
if(l<=r):
lists=*60
fib(lists,l,r)
else:
print(-1)

``````
Tester's Solution
``````
from collections import defaultdict, deque
from itertools import permutations
from sys import stdin,stdout
from bisect import bisect_left, bisect_right
from copy import deepcopy
import heapq

string_list_input=lambda: list(string_input())
MOD = pow(10,9)+7

fibo = []

def findFiboSum():
count = 1
a = 0
b = 1
fibo.append(a)
fibo.append(b)

while(count <= 10000001):
count+=1
fibo.append((fibo[count-1]+fibo[count-2])%10)

for i in range(1, len(fibo)):
fibo[i] = fibo[i] + fibo[i-1]

findFiboSum()

test = int_input()

for _ in range(test):
l, r = multi_int_input()

if (l>r):
print(-1)
elif l == 0:
print(fibo[r])
else:
print((fibo[r] - fibo[l-1]))
``````
2 Likes