summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--AlgoDesignAndTechniqueEdxPython/sources/fibagain.py14
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()