diff options
| -rw-r--r-- | AlgoDesignAndTechniqueEdxPython/sources/fibagain.py | 14 |
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() |