Last digit of Fib sum is done.

2 files changed, 55 insertions, 0 deletions

diff --git a/AlgoDesignAndTechniqueEdxPython/sources/lastdigitoffibsum.py b/AlgoDesignAndTechniqueEdxPython/sources/lastdigitoffibsum.py
new file mode 100644
index 0000000..b48748e
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/sources/lastdigitoffibsum.py
@@ -0,0 +1,33 @@
+# 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
+
+if __name__ == '__main__':
+    input = sys.stdin.read()
+    n = int(input)
+    print(getLastDigit(n))
\ No newline at end of file
diff --git a/AlgoDesignAndTechniqueEdxPython/tests/lastdigitoffibsumTest.py b/AlgoDesignAndTechniqueEdxPython/tests/lastdigitoffibsumTest.py
new file mode 100644
index 0000000..c1d83b6
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/tests/lastdigitoffibsumTest.py
@@ -0,0 +1,22 @@
+'''
+Created on Aug 28, 2018
+
+@author: haidong
+'''
+import unittest
+from sources.lastdigitoffibsum import getLastDigit
+
+class Test(unittest.TestCase):
+
+
+    def testName(self):
+        self.assertEqual(0, getLastDigit(0))
+        self.assertEqual(1, getLastDigit(1))
+        self.assertEqual(0, getLastDigit(6))
+        self.assertEqual(8, getLastDigit(9))
+        self.assertEqual(5, getLastDigit(100))
+
+
+if __name__ == "__main__":
+    #import sys;sys.argv = ['', 'Test.testName']
+    unittest.main()
\ No newline at end of file