summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--AlgoDesignAndTechniqueEdxPython/sources/fibagain.py64
-rw-r--r--AlgoDesignAndTechniqueEdxPython/tests/fibagainTest.py13
2 files changed, 48 insertions, 29 deletions
diff --git a/AlgoDesignAndTechniqueEdxPython/sources/fibagain.py b/AlgoDesignAndTechniqueEdxPython/sources/fibagain.py
index 53c18b9..86b5152 100644
--- a/AlgoDesignAndTechniqueEdxPython/sources/fibagain.py
+++ b/AlgoDesignAndTechniqueEdxPython/sources/fibagain.py
@@ -1,27 +1,29 @@
# Uses python3
import sys
-def getFib(n):
- if (n <= 1):
- return n
- fibLst = [None] * (n + 1)
- fibLst[0] = 0
- fibLst[1] = 1
- for j in range(2, n + 1):
- 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 getFib(n):
+# if (n <= 1):
+# return n
+# fibLst = [None] * (n + 1)
+# fibLst[0] = 0
+# fibLst[1] = 1
+# for j in range(2, n + 1):
+# 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 _ in range(2, n + 1):
+# tempHolder = firstFib + secondFib
+# firstFib = secondFib
+# secondFib = tempHolder
+# return secondFib
def getPisanoPeriod(m):
@@ -29,7 +31,7 @@ def getPisanoPeriod(m):
remainder1 = 1
remainder2 = 1
- for i in range(3, 6 * m + 1):
+ for _ in range(3, 6 * m + 1):
period = period + 1
if (remainder2 == 1) & (remainder1 + remainder2 == m):
break
@@ -45,12 +47,26 @@ def getPisanoPeriod(m):
def getFibNModM(n, m):
+ # https://medium.com/competitive/huge-fibonacci-number-modulo-m-6b4926a5c836
+ # the above link helped me in improving my code
p = getPisanoPeriod(m)
- return getFibOptimized(n % p) % m
+ r = n % p
+ if r == 0:
+ return 0
+ firstN = 0
+ secondN = 1
+ tempHolder = 1
+ for _ in range(2, r + 1):
+ tempHolder = (firstN + secondN) % m;
+ firstN = secondN
+ secondN = tempHolder
+# return getFibOptimized(n % p) % m
+ return secondN
+
if __name__ == '__main__':
entryNumbers = sys.stdin.read()
tokens = entryNumbers.split()
n = int(tokens[0])
m = int(tokens[1])
- print(getFibNModM(n, m)) \ No newline at end of file
+ print(getFibNModM(n, m))
diff --git a/AlgoDesignAndTechniqueEdxPython/tests/fibagainTest.py b/AlgoDesignAndTechniqueEdxPython/tests/fibagainTest.py
index edcc5ba..2702bdb 100644
--- a/AlgoDesignAndTechniqueEdxPython/tests/fibagainTest.py
+++ b/AlgoDesignAndTechniqueEdxPython/tests/fibagainTest.py
@@ -12,22 +12,25 @@ class Test(unittest.TestCase):
def testPisanoPeriod73(self):
self.assertEqual(getPisanoPeriod(73), 148)
-
+
def testPisanoPeriod2(self):
self.assertEqual(getPisanoPeriod(2), 3)
-
+
def testPisanoPeriod98(self):
self.assertEqual(getPisanoPeriod(98), 336)
-
+
def testFibNModM2015_3(self):
self.assertEqual(getFibNModM(2015, 3), 1)
-
+
def testFibNModM239_1000(self):
self.assertEqual(getFibNModM(239, 1000), 161)
-
+
def testFibNModM2816213588_30524(self):
self.assertEqual(getFibNModM(2816213588, 30524), 10249)
+ def testFibNModM99999999999999999_2(self):
+ self.assertEqual(getFibNModM(99999999999999999, 2), 0)
+
if __name__ == "__main__":
#import sys;sys.argv = ['', 'Test.testName']
unittest.main() \ No newline at end of file