Improved code by getting rid of array during fib calculation

1 files changed, 13 insertions, 1 deletions

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()