From b4c46291059c52396aa4edb6cf96e66d10b17ccd Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Tue, 28 Aug 2018 19:52:26 -0500
Subject: Last digit of Fib sum is done.

---
 .../sources/lastdigitoffibsum.py                   | 33 ++++++++++++++++++++++
 1 file changed, 33 insertions(+)
 create mode 100644 AlgoDesignAndTechniqueEdxPython/sources/lastdigitoffibsum.py

(limited to 'AlgoDesignAndTechniqueEdxPython/sources')

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
-- 
cgit v1.2.3