Given two integers a and b, find:
gcd(a, b)an integer
xan integer
y
such that: ax + by = gcd(a, b) Return all three values.
Example 1
Input: a = 35, b = 15
Output: gcd = 5, x = 1, y = -2
Explanation: 35 * 1 + 15 * (-2) = 5
So the gcd is 5, and one valid pair of coefficients is (1, -2).
Example 2
Input: a = 30, b = 20
Output: gcd = 10, x = 1, y = -1
Explanation: 30 * 1 + 20 * (-1) = 10
So the gcd is 10, and one valid pair of coefficients is (1, -1).
Approach
The normal Euclidean Algorithm keeps replacing: (a, b) -> (b, a % b) because both pairs have the same gcd. The extended version keeps the same shrinking idea, but also tracks how the current gcd can be written using the original numbers. Suppose the recursive call already solves the smaller problem: b * x1 + (a % b) * y1 = gcd Now replace a % b with: a % b = a - (a / b) * b Then: gcd = b * x1 + (a - (a / b) * b) * y1 After rearranging: gcd = a * y1 + b * (x1 - (a / b) * y1) That directly gives the new coefficients:
x = y1y = x1 - (a / b) * y1
This is the whole trick. The recursive call solves a smaller remainder problem, and then the answer is translated back to the current pair.
Algorithm
If
bbecomes0, stop the recursion and returngcd = |a|. This is the base case because once the second number becomes0, the first number already holds the gcd.At that base case, return coefficients that make the equation true immediately. For a positive
a, that can bex = 1andy = 0, becausea * 1 + 0 * 0 = a.Otherwise, solve the smaller problem
(b, a % b)first. This is done because the Euclidean Algorithm guarantees that both pairs have the same gcd.Let the recursive call return coefficients for the smaller equation. These coefficients are correct for
banda % b, but not yet for the currentaandb.Convert those smaller coefficients into the current coefficients using: x = y1 and y = x1 - (a / b) * y1
Return the updated
gcd,x, andy.
Dry Run
Extended Euclidean Algorithm Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: struct Result { long long gcd; long long x; long long y; };private: /* Solves the extended Euclidean relation for non-negative values and returns gcd, x, and y such that ax + by = gcd. */ Result extendedEuclidHelper(long long a, long long b) { /* When b becomes 0, the current a already holds the gcd. The coefficients 1 and 0 make the equation true here. */ if (b == 0) { return {a, 1, 0}; } /* First solve the smaller remainder problem because gcd(a, b) is the same as gcd(b, a % b). */ Result next = extendedEuclidHelper(b, a % b); /* The current x comes from the smaller y because the smaller equation is being rewritten in terms of a and b. */ long long currentX = next.y; /* The current y removes the quotient contribution created by replacing a % b with a - (a / b) * b. */ long long currentY = next.x - (a / b) * next.y; return {next.gcd, currentX, currentY}; }public: // Finds gcd, x, and y such that ax + by = gcd(a, b). Result extendedEuclid(long long a, long long b) { // Return a safe all-zero result for the special 0,0 case. if (a == 0 && b == 0) { return {0, 0, 0}; } /* Keep the original signs so the final coefficients can be adjusted back to match the given inputs. */ long long originalA = a; long long originalB = b; /* Work with non-negative values so the recursive remainder logic stays simple and consistent. */ a = llabs(a); b = llabs(b); // Solve the problem for absolute values first. Result answer = extendedEuclidHelper(a, b); /* If the original a was negative, flip x so the final linear combination still matches the original sign. */ if (originalA < 0) { answer.x = -answer.x; } /* If the original b was negative, flip y for the same sign-correction reason. */ if (originalB < 0) { answer.y = -answer.y; } return answer; }};// Driver code starts int main() { long long a = 35; long long b = 15; Solution sol; Solution::Result result = sol.extendedEuclid(a, b); cout << "gcd = " << result.gcd << ", x = " << result.x << ", y = " << result.y << endl; return 0;}Complexity Analysis
Time Complexity: O(log(min(|a|, |b|))), because the remainder-based reduction shrinks the numbers quickly.
Space Complexity: O(log(min(|a|, |b|))), because the recursive call stack stores one frame for each Euclidean reduction step.
Interview follow-up Questions
It returns those values because the goal is not only to find the gcd, but also to express that gcd as ax + by.
Be the first to add a comment.