Extended Euclidean Algorithm

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
20 upvotes
Asked in companies
UberGoogle inc

Problem statement

You have just been taught about linear equations and about GCD(Greatest Common Divisor). So, you are given an equation AX + BY = C where A and B are two integers that you are given and D is the GCD or greatest common divisors of A and B.


So, you have to find out 2 integers x and y such that the above equation is satisfied for C = D, |X+Y| is minimum. If there are multiple such pairs, return the one where X is maximum.


Example:- 
A = 2
B = 4
The answer should be D = 2 [gcd of (2,4)] and X = 1  and Y = 0 (|X+Y|=1 is the minimum possible value that can be obtained here).
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ representing the number of test cases. Then each test case follows.

The first line of every test case contains two integers ‘A’ and ‘B’ denoting the 2 coefficients.
Output Format : 
For each test case, print three integers ‘D’, ‘X’, and ‘Y’ where ‘D’ is the gcd of ‘A’ and ‘B’ and ‘X’ and ‘Y’ are the two coefficients that satisfy the equation AX + BY = D.

The output of each test case should be printed in a separate line.
Note : 
You are not required to print anything, it has already been taken care of. Just implement the function.
Constraints : 
1 <= T <= 10
1 <= A <= 10^9
1 <= B <= 10^9

Time Limit = 1 sec
Sample Input 1 :
2
4 6
17 17
Sample Output 1 :
2 -1 1
17 1 0
Explanation for Sample Output 1 :
In the first test case, the GCD of 4 and 6 is 2. So, X=-1 and Y=1 satisfy the equation AX+BY=D with |X+Y| being minimum.

In the second test case, the GCD of 17 and 17 is 17. So, X=1 and Y=0 satisfy the equation AX+BY=D with |X+Y| being minimum.
Note that X=0,Y=1 also satisfies the equation with minimum |X+Y| but the value of X is smaller.
Sample Input 2 :
1
1 1
Sample Output 2 :
1 1 0
Hint

Use the extended euclidean algorithm.

Approaches (1)
Extended Euclidean Algorithm

Use the Euclidean algorithm to find the gcd of A and B first and then use the extended euclidean algorithm to find the coefficients of the equation.

 

More about Euclidean algorithm - https://cp-algorithms.com/algebra/euclid-algorithm.html

 

Algorithm:-

 

  1. Define a function named extended_euclidean_algo with A and B as parameters.
    1. If A is equal to 0, return the tuple (B, 0, 1).
    2. Else store the value returned by euclidean_algo with B%A and A as parameters in D, X, and Y.
    3. Update X as Y minus b divided by a multiplied by X.
    4. Update Y as X.
  2. Store the value returned by euclidean_algo with A and B as parameters in D, X, and Y.
  3. Return D, X, and Y.
Time Complexity

O(log (min(A, B))), where A and B are the two integers provided.

We are applying the Euclidean algorithm on A and B which takes log (min(A, B)) time, so the time complexity is O(log(min(A, B)).

Space Complexity

O(log (min(A, B))), where A and B are the two integers provided,

We are forming a recursion stack that can grow up to a size of log min(m,n), so the space complexity is O(log(min(A, B))).

Code Solution
(100% EXP penalty)
Extended Euclidean Algorithm
Full screen
Console