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++

## What is the Extended Euclid's algorithm?
*The Extended Euclid’s algorithm* is used to find the solution of equations of the form Ax + By = C , where C is a
multiple of divisor of A and B, or in other words `C = gcd(A, B)`. Extended Euclid’s works in the same manner as the Euclid’s algorithm.
Let the equation be `Ax + By = 1` (let the solutions of this equation be x’ and y’). We have been given that `gcd(A, B)` is `1`, then
the solutions of equation `Ax + By = k` where `k` is a multiple of `gcd(A, B)` are given by `k*x’` and `k*y’`.

Now we can write:
```
A.x + B.y = gcd(A, B)       ----(1)  
```
Using the Euclid’s algorithm that we discussed earlier, we know that `gcd(A, B) = gcd(B, A % B)`. Hence, we can write the above equation as:
```
B.x1 + (A % B).y1 = gcd(B, A % B)
```                    
When we put `(A % B) = (A - (floor(A/B)).B)` in the above equation, we get the following: 
```
B.x1 + (A - floor(A/B).B).y1 = gcd(B, A % B)
```
The above equation can also be written like this:
```
B.(x1 - floor(A/B).y1) + A.y1 = gcd     ---(2)
```
After comparing coefficients of 'A' and 'B' in (1) and 
(2), we get the following:
```
x = y1
y = x1 – floor(A/B).y1
```

Now, let's move to the implementation.



# What is the Extended Euclid's algorithm?
*The Extended Euclid’s algorithm* is used to find the solution of equations of the form Ax + By = C , where C is a
multiple of divisor of A and B, or in other words `C = gcd(A, B)`. Extended Euclid’s works in the same manner as the Euclid’s algorithm.
Let the equation be `Ax + By = 1` (let the solutions of this equation be x’ and y’). We have been given that `gcd(A, B)` is `1`, then
the solutions of equation `Ax + By = k` where `k` is a multiple of `gcd(A, B)` are given by `k*x’` and `k*y’`.

Now we can write:
```
A.x + B.y = gcd(A, B)       ----(1)  
```
Using the Euclid’s algorithm that we discussed earlier, we know that `gcd(A, B) = gcd(B, A % B)`. Hence, we can write the above equation as:
```
B.x1 + (A % B).y1 = gcd(B, A % B)
```                    
When we put `(A % B) = (A - (floor(A/B)).B)` in the above equation, we get the following: 
```
B.x1 + (A - floor(A/B).B).y1 = gcd(B, A % B)
```
The above equation can also be written like this:
```
B.(x1 - floor(A/B).y1) + A.y1 = gcd     ---(2)
```
After comparing coefficients of 'A' and 'B' in (1) and 
(2), we get the following:
```
x = y1
y = x1 – floor(A/B).y1
```

Now, let's move to the implementation.



Learn the Extended Euclid's algorithm that can be used to solve equations of the form Ax + By = C.

Overview

Number Theory

Number Theory

Divide and Conquer

Greedy Algorithms

Greedy Algorithms

Recursion and Backtracking

Recursion and Backtracking

Dynamic Programming

Graphs

Bonus Lessons

Extended Euclid's Algorithm

What is the Extended Euclid’s algorithm?