Hard · Extended Euclidean Algorithm
Understand → Visualise → Practice.
Return `[gcd,x,y]` satisfying `a×x + b×y = gcd(a,b)` for non-negative inputs.
Run the Euclidean algorithm, but carry coefficients (s, t) for every remainder so that remainder = a × s + b × t. The last non-zero remainder is the gcd.
(old_r, old_s, old_t) = (a, 1, 0) and (r, s, t) = (b, 0, 1).
With q = old_r // r, update each pair as (new, old) = (old − q × new, new).
When r reaches 0, return [old_r, old_s, old_t].
O(log min(a, b)) time and O(1) space.
Updating r before computing s and t with the same q mixes up the steps; update all three pairs with one q.
Read the full guide first: Number Theory Basics for Algorithms.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.