Repository: keon/algorithms
Pull request #721 (2020-10-04 19:20:23)

Added Modular Inverse


Patch:
diff --git a/README.md b/README.md
index 7aaafc1..a20a740 100644
--- a/README.md
+++ b/README.md
@@ -210,6 +210,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [generate_strobogrammtic](algorithms/maths/generate_strobogrammtic.py)
     - [is_strobogrammatic](algorithms/maths/is_strobogrammatic.py)
     - [modular_exponential](algorithms/maths/modular_exponential.py)
+    - [modular_inverse](algorithms/maths/modular_inverse.py)
     - [next_bigger](algorithms/maths/next_bigger.py)
     - [next_perfect_square](algorithms/maths/next_perfect_square.py)
     - [nth_digit](algorithms/maths/nth_digit.py)
diff --git a/algorithms/maths/modular_inverse.py b/algorithms/maths/modular_inverse.py
new file mode 100644
index 0000000..f53d0f6
--- /dev/null
+++ b/algorithms/maths/modular_inverse.py
@@ -0,0 +1,34 @@
+# extended_gcd(a, b) modified from 
+# https://github.com/keon/algorithms/blob/master/algorithms/maths/extended_gcd.py 
+
+def extended_gcd(a: int, b: int) -> [int, int, int]:
+    """Extended GCD algorithm.
+    Return s, t, g
+    such that a * s + b * t = GCD(a, b)
+    and s and t are co-prime.
+    """
+
+    old_s, s = 1, 0
+    old_t, t = 0, 1
+    old_r, r = a, b
+    
+    while r != 0:
+        quotient = old_r // r
+        
+        old_r, r = r, old_r - quotient * r
+        old_s, s = s, old_s - quotient * s
+        old_t, t = t, old_t - quotient * t
+    
+    return old_s, old_t, old_r
+
+
+def modular_inverse(a: int, m: int) -> int:
+    """
+    Returns x such that a * x = 1 (mod m)
+    a and m must be coprime 
+    """
+
+    s, t, g = extended_gcd(a, m)
+    if g != 1:
+        raise ValueError("a and m must be coprime")
+    return s % m
diff --git a/algorithms/tree/red_black_tree/red_black_tree.py b/algorithms/tree/red_black_tree/red_black_tree.py
index 6ced71e..4b3c0d6 100644
--- a/algorithms/tree/red_black_tree/red_black_tree.py
+++ b/algorithms/tree/red_black_tree/red_black_tree.py
@@ -241,8 +241,7 @@ class RBTree:
                     node.parent.color = 0
                     node_brother.right.color = 0
                     self.left_rotate(node.parent)
-                node = self.root
-                break
+                    node = self.root
             else:
                 node_brother = node.parent.left
                 if node_brother.color == 1:
@@ -264,8 +263,7 @@ class RBTree:
                     node.parent.color = 0
                     node_brother.left.color = 0
                     self.right_rotate(node.parent)
-                node = self.root
-                break
+                    node = self.root
         node.color = 0
 
     def inorder(self):


Test patch:
diff --git a/tests/test_maths.py b/tests/test_maths.py
index a79c690..7667488 100644
--- a/tests/test_maths.py
+++ b/tests/test_maths.py
@@ -8,6 +8,7 @@ from algorithms.maths import (
     gcd, lcm, trailing_zero, gcd_bit,
     gen_strobogrammatic, strobogrammatic_in_range,
     is_strobogrammatic, is_strobogrammatic2,
+    modular_inverse,
     modular_exponential,
     find_next_square, find_next_square2,
     prime_check,
@@ -166,6 +167,21 @@ class TestIsStrobogrammatic(unittest.TestCase):
         self.assertFalse(is_strobogrammatic2("14"))
 
 
+class TestModularInverse(unittest.TestCase):
+    """[summary]
+    Test for the file modular_Exponential.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """    
+
+    def test_modular_inverse(self):
+        # checks if x * x_inv == 1 (mod m)
+        self.assertEqual(1, 2 * modular_inverse.modular_inverse(2, 19) % 19)
+        self.assertEqual(1, 53 * modular_inverse.modular_inverse(53, 91) % 91)
+        self.assertEqual(1, 2 * modular_inverse.modular_inverse(2, 1000000007) % 1000000007)
+        self.assertRaises(ValueError, modular_inverse.modular_inverse, 2, 20)
+
 class TestModularExponential(unittest.TestCase):
     """[summary]
     Test for the file modular_Exponential.py