The ultimate guide to coding interviews. Developed by FAANG engineers. Boost problem-solving skills with number theory, dynamic programming, and graph theory. Get interview-ready in just a few hours.

Competitive Programming - Crack Your Coding Interview.png

Whether you’re gearing up for online coding challenges, code-a-thons, or interviews, then this course is for you. With this course, you will solidify your problem-solving skills ensuring a swift sail through any problem. 


You will be tasked with solving some of the most frequently asked questions that are brought up in FAANG interviews. You will start with the concepts of Number Theory and Divide and Conquer, and gradually move towards more complex problems like dynamic programming and graph theory.


With each problem you solve, there will be insightful explanations and full implementation details to really hammer home the concepts. By the time you finish this course, you will have the confidence to solve any problem, no matter the difficulty.

Competitive Programming - Crack Your Coding Interview, C++

## Problem introduction
Write a program to calculate the multiplicative modulo inverse of `A` with respect to `M`. The modular multiplicative inverse is an integer `x` such that. 
```
A x ≅ 1 (mod M) 
```
The multiplicative inverse of `A modulo M` exists if, and only if, `A` and `M` are relatively prime, i.e., `gcd(A, M) = 1`. The value of `x` should be in `{0, 1, 2, … M-1}.` 

Let us take the following example: `A = 3`, `M = 11`, so the output will be `x = 4` since `(4*3) mod 11 = 1`, `4` is modulo inverse of 3 with respect to 11.
You might think, `15` also as a valid output as `(15*3) mod 11` 
is also 1, but 15 is not in the ring `{0, 1, 2, ... 10}`, so it is not valid.

Let us see how the Extended Euclid's algorithm can be used in this case.
We know from the Extended Euclid's algorithm that: 
```
A.x + B. y = gcd(A, B)
```
To find the multiplicative inverse of `A` under `M`, we put `B = M` in the above formula. Since we know that `A` and `M` are relatively prime, we can put the value of `gcd` as 1.
```
A.x + M.y = 1 
```
If we take `modulo M` on both sides, we get
```
A.x + M.y ≅ 1 (mod M)
```
We can remove the second term on the left side as `M.y (mod M)` would always be 0 for an integer `y`. 
```
A.x  ≅ 1 (mod M) 
```
So the `x` that we can find using the Extended Euclid algorithm is the multiplicative inverse of `A`.

## Solution
Now, let us move on to the implementation of this solution.

# Problem introduction
Write a program to calculate the multiplicative modulo inverse of `A` with respect to `M`. The modular multiplicative inverse is an integer `x` such that. 
```
A x ≅ 1 (mod M) 
```
The multiplicative inverse of `A modulo M` exists if, and only if, `A` and `M` are relatively prime, i.e., `gcd(A, M) = 1`. The value of `x` should be in `{0, 1, 2, … M-1}.` 

Let us take the following example: `A = 3`, `M = 11`, so the output will be `x = 4` since `(4*3) mod 11 = 1`, `4` is modulo inverse of 3 with respect to 11.
You might think, `15` also as a valid output as `(15*3) mod 11` 
is also 1, but 15 is not in the ring `{0, 1, 2, ... 10}`, so it is not valid.

Let us see how the Extended Euclid's algorithm can be used in this case.
We know from the Extended Euclid's algorithm that: 
```
A.x + B. y = gcd(A, B)
```
To find the multiplicative inverse of `A` under `M`, we put `B = M` in the above formula. Since we know that `A` and `M` are relatively prime, we can put the value of `gcd` as 1.
```
A.x + M.y = 1 
```
If we take `modulo M` on both sides, we get
```
A.x + M.y ≅ 1 (mod M)
```
We can remove the second term on the left side as `M.y (mod M)` would always be 0 for an integer `y`. 
```
A.x  ≅ 1 (mod M) 
```
So the `x` that we can find using the Extended Euclid algorithm is the multiplicative inverse of `A`.

# Solution
Now, let us move on to the implementation of this solution.

Use the Extended Euclid's algorithm to calculate the modular multiplicative inverse of a number.

Overview

Number Theory

Number Theory

Divide and Conquer

Greedy Algorithms

Greedy Algorithms

Recursion and Backtracking

Recursion and Backtracking

Dynamic Programming

Graphs

Bonus Lessons

Modular Multiplicative Inverse Using EEA

Problem introduction