1 files changed, 40 insertions, 24 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))