ENCJMAY5 - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Practice
Contest Link

Author: Abhishek Kumar
Tester: Sandeep Singh,Arnab Chanda

DIFFICULTY:

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]=0
    lists[1]=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=[0]*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
 
int_input=lambda : int(stdin.readline())
string_input=lambda : stdin.readline().split()
multi_int_input =lambda : map(int, stdin.readline().split())
multi_input = lambda : stdin.readline().split()
list_input=lambda : list(map(int,stdin.readline().split()))
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