diff options
Diffstat (limited to 'AlgoDesignAndTechniqueEdxPython/sources/lastdigitoffibsumagain.py')
-rw-r--r-- | AlgoDesignAndTechniqueEdxPython/sources/lastdigitoffibsumagain.py | 52 |
1 files changed, 52 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxPython/sources/lastdigitoffibsumagain.py b/AlgoDesignAndTechniqueEdxPython/sources/lastdigitoffibsumagain.py new file mode 100644 index 0000000..21de833 --- /dev/null +++ b/AlgoDesignAndTechniqueEdxPython/sources/lastdigitoffibsumagain.py @@ -0,0 +1,52 @@ +# Uses python3 +import sys + +FIB_PISANO_PERIOD_FOR_TEN = 60; + +def getFibNModM(n): + r = n % FIB_PISANO_PERIOD_FOR_TEN + if r==0: + return 0 + firstN = 0 + secondN = 1 + tempHolder = 1 + + for _ in range(2, r + 1): + tempHolder = (firstN + secondN) % 10; + firstN = secondN + secondN = tempHolder +# return getFibOptimized(n % p) % m + return secondN + + +def getLastDigit(n): + if n<=1: + return n + result = getFibNModM(n+2) + if result==0: + return 9 + else: + return result -1 + +def getPartialSumLastDigit(m, n): + if m==n: + return getFibNModM(n) + else: + sumFn=getLastDigit(n) + if m<=1: + sumFm = 0 + else: + sumFm = getLastDigit(m-1) + if sumFn>=sumFm: + return sumFn-sumFm + else: + return sumFn - sumFm + 10 + +if __name__ == '__main__': + input = sys.stdin.read() + tokens = input.split() + m = int(tokens[0]) + n = int(tokens[1]) + print(getPartialSumLastDigit(m, n)) + + |