blob: cca9cd98602714e2cbfdda44a101faa6ab11ad61 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
# Uses python3
import sys
def getFibLastDigitNaive(n):
if n <= 1:
return n
previous = 0
current = 1
for _ in range(n - 1):
previous, current = current, previous + current
return current % 10
def getFibLastDigitOptimized(n):
if (n <= 1):
return n
fibLst = [None] * (n+1)
fibLst[0] = 0
fibLst[1] = 1
for i in range(2, n+1):
fibLst[i] = (fibLst[i-1] + fibLst[i-2]) % 10
return fibLst[n]
if __name__ == '__main__':
input = sys.stdin.read()
n = int(input)
print(getFibLastDigitOptimized(n))
|