Given two integers ‘a’ and ‘m’. The task is to find the smallest modular multiplicative inverse of ‘a’ under modulo ‘m’.
 
Example 1:
Input:
a = 3
m = 11
Output: 4
Explanation: Since (4*3) mod 11 = 1, 4 
is modulo inverse of 3. One might think,
15 also as a valid output as "(15*3)
mod 11"  is also 1, but 15 is not in 
ring {0, 1, 2, ... 10}, so not valid.
 
Example 2:
Input:
a = 10
m = 17
Output: 12
Explanation: Since (12*10) mod 17 = 1,
12 is the modulo inverse of 10.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function  function modInverse() that takes a and m as input parameters and returns modular multiplicative inverse of ‘a’ under modulo ‘m’. If the modular multiplicative inverse doesn't exist return -1.
 
Expected Time Complexity : O(m)
Expected Auxilliary Space : O(1)
 
Constraints:
1 <= a <= 10^{4}
1 <= m <= 10^{4}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3

class Solution:    
    ##Complete this function
    def modInverse(self,a,m):
        ##Your code here

Solutions:
class Solution:

	def modInverse(self, a, m):
		for i in range(1, m):
			if a % m * (i % m) % m == 1:
				return i
		return -1


import math

class Solution:

	def modInverse(self, a, m):
		if m <= 1:
			return -1
		if math.gcd(a, m) == 1:
			for i in range(1, m):
				if a * i % m == 1:
					return i
		else:
			return -1


class Solution:

	def modInverse(self, a, m):
		for x in range(0, m):
			if a * x % m == 1:
				return x
		else:
			return -1


class Solution:

	def modInverse(self, a, m):
		num = 1
		while num < m:
			if a * num % m == 1:
				return num
			num += 1
		return -1


class Solution:

	def extended_gcd(self, a, b):
		if a == 0:
			return (b, 0, 1)
		else:
			(gcd, x, y) = self.extended_gcd(b % a, a)
			return (gcd, y - b // a * x, x)

	def modInverse(self, a, m):
		if math.gcd(a, m) != 1:
			return -1
		else:
			(gcd, x, y) = self.extended_gcd(a, m)
			return (x % m + m) % m if m > 1 else -1


class Solution:

	def modInverse(self, a, m):
		res = 0
		while res < m:
			if a * res % m == 1:
				return res
			res += 1
		return -1


class Solution:

	def modInverse(self, a, m):
		b = 0
		i = 0
		while i < m:
			if i * a % m == 1:
				b = i
				break
			i += 1
		if a * b % m == 1:
			return b
		else:
			return -1


from math import gcd

class Solution:

	def modInverse(self, a, m):
		if a % m == 0 or gcd(a, m) != 1:
			return -1
		f = 1
		i = 1
		while f == 1:
			if a * i % m == 1:
				return i
			i += 1


class Solution:

	def modInverse(self, a, m):
		b = 0
		res = a * b % m
		out = -1
		for i in range(m):
			res = a * i % m
			if res == 1:
				out = i
				break
		return out


class Solution:

	def modInverse(self, a, m):
		b = 1
		while b < m:
			if a * b % m == 1:
				return b
			b = b + 1
		return -1


class Solution:

	def modInverse(self, a, m):
		l = range(0, m)
		for b in range(0, m):
			if b * a % m == 1:
				return b
		return -1


class Solution:

	def modInverse(self, a, m):
		if a % m == 0:
			return -1
		start = 1
		while start < m:
			if start * a % m == 1:
				return start
			else:
				start += 1
		return -1


class Solution:

	def modInverse(self, a, m):
		mini = 65845646854654
		num = 0
		for i in range(m):
			n = i * a % m
			if n <= mini and n == 1:
				mini = n
				num = i
		if num > 0:
			return num
		return -1


class Solution:

	def modInverse(self, A, M):
		for X in range(1, M):
			if A % M * (X % M) % M == 1:
				return X
		return -1


class Solution:

	def modInverse(self, a, m):
		i = 1
		while i < m:
			if i * a % m == 1:
				return i
			i += 1
		return -1


class Solution:

	def modInverse(self, a, m):
		res = 0
		for num in range(1, m):
			res = a % m * (num % m) % m
			if res == 1:
				return num
		return -1


from math import gcd

class Solution:

	def modInverse(self, a, m):
		if a % m == 0 or gcd(a, m) != 1:
			return -1
		for I in range(1, m):
			if a * I % m == 1:
				return I


class Solution:

	def modInverse(self, a, m):
		ans = m
		prev = m
		for i in range(1, m):
			curr = i * a % m
			if curr == 1:
				return i
		return -1