From 3bd8d9ca47715f9d808f6e42aefdbaffb8a29923 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Fri, 24 Aug 2018 13:51:30 -0500
Subject: Improved code by getting rid of array during fib calculation

---
 AlgoDesignAndTechniqueEdxPython/sources/fibagain.py | 14 +++++++++++++-
 1 file changed, 13 insertions(+), 1 deletion(-)

diff --git a/AlgoDesignAndTechniqueEdxPython/sources/fibagain.py b/AlgoDesignAndTechniqueEdxPython/sources/fibagain.py
index 2f2c839..53c18b9 100644
--- a/AlgoDesignAndTechniqueEdxPython/sources/fibagain.py
+++ b/AlgoDesignAndTechniqueEdxPython/sources/fibagain.py
@@ -11,6 +11,18 @@ def getFib(n):
         fibLst[j] = fibLst[j - 1] + fibLst[j - 2]
     return fibLst[n]
 
+def getFibOptimized(n):
+    if (n <= 1):
+        return n
+    firstFib = 0
+    secondFib = 1
+    tempHolder = 1
+    for j in range(2, n + 1):
+        tempHolder = firstFib + secondFib
+        firstFib = secondFib
+        secondFib = tempHolder
+    return secondFib
+
 
 def getPisanoPeriod(m):
     period = 2
@@ -34,7 +46,7 @@ def getPisanoPeriod(m):
 
 def getFibNModM(n, m):
     p = getPisanoPeriod(m)
-    return getFib(n % p) % m
+    return getFibOptimized(n % p) % m
 
 if __name__ == '__main__':
     entryNumbers = sys.stdin.read()
-- 
cgit v1.2.3