From a6fbcd67ecf83f4715a7fff4ae52cdf91687c8d6 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Wed, 29 Aug 2018 16:24:08 -0500
Subject: Last digit of partial fib sums done

It was pretty easy, just reimplemting the algorithm I've finished with
Java.---
 .../sources/lastdigitoffibsumagain.py              | 52 ++++++++++++++++++++++
 .../tests/lastdigitoffibsumagainTest.py            | 25 +++++++++++
 2 files changed, 77 insertions(+)
 create mode 100644 AlgoDesignAndTechniqueEdxPython/sources/lastdigitoffibsumagain.py
 create mode 100644 AlgoDesignAndTechniqueEdxPython/tests/lastdigitoffibsumagainTest.py

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))
+
+
diff --git a/AlgoDesignAndTechniqueEdxPython/tests/lastdigitoffibsumagainTest.py b/AlgoDesignAndTechniqueEdxPython/tests/lastdigitoffibsumagainTest.py
new file mode 100644
index 0000000..48af95f
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/tests/lastdigitoffibsumagainTest.py
@@ -0,0 +1,25 @@
+'''
+Created on Aug 29, 2018
+
+@author: haidong
+'''
+import unittest
+
+from sources.lastdigitoffibsumagain import getPartialSumLastDigit
+
+class Test(unittest.TestCase):
+
+
+    def testName(self):
+        self.assertEqual(5, getPartialSumLastDigit(5,5))
+        self.assertEqual(1, getPartialSumLastDigit(3,7))
+        self.assertEqual(2, getPartialSumLastDigit(10,200))
+        self.assertEqual(6, getPartialSumLastDigit(5,7))
+        self.assertEqual(7, getPartialSumLastDigit(5,8))
+        self.assertEqual(1, getPartialSumLastDigit(5,9))
+        self.assertEqual(2, getPartialSumLastDigit(1,2))
+
+
+if __name__ == "__main__":
+    #import sys;sys.argv = ['', 'Test.testName']
+    unittest.main()
\ No newline at end of file
-- 
cgit v1.2.3