From 18030db87580ab02962686509f65c7e1cfcd2d4c Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Thu, 16 Aug 2018 22:18:18 -0500
Subject: Fib last digit done. Yay!

Bonus: figured PyDev TDD code generation issue. I created "sources" as a source folder, but really should have created as a package, for TDD code generation to work properly. Fixed now!---
 .../sources/__init__.py                            |  0
 .../sources/fiblastdigit.py                        | 29 ++++++++++++++++++++++
 2 files changed, 29 insertions(+)
 create mode 100644 AlgoDesignAndTechniqueEdxPython/sources/__init__.py
 create mode 100644 AlgoDesignAndTechniqueEdxPython/sources/fiblastdigit.py

(limited to 'AlgoDesignAndTechniqueEdxPython/sources')

diff --git a/AlgoDesignAndTechniqueEdxPython/sources/__init__.py b/AlgoDesignAndTechniqueEdxPython/sources/__init__.py
new file mode 100644
index 0000000..e69de29
diff --git a/AlgoDesignAndTechniqueEdxPython/sources/fiblastdigit.py b/AlgoDesignAndTechniqueEdxPython/sources/fiblastdigit.py
new file mode 100644
index 0000000..cca9cd9
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/sources/fiblastdigit.py
@@ -0,0 +1,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))
-- 
cgit v1.2.3