GCD, LCM and Fraction Problems in Coding Interviews: Euclid's Algorithm and Its Uses
3 views
Number theory questions are less common than arrays and graphs, but the greatest common divisor appears inside many interview problems: simplifying fractions, finding when two cycles align, rotating arrays in blocks, or checking whether a jug can measure a certain amount. Knowing Euclid's algorithm well makes these problems short.
Euclid's algorithm
The idea: gcd(a, b) = gcd(b, a mod b), and gcd(a, 0) = a.
def gcd(a, b):
while b:
a, b = b, a % b
return abs(a)
It runs in O(log(min(a, b))) steps, because the remainder at least halves every two iterations. Interviewers sometimes ask why; mention that worst-case inputs are consecutive Fibonacci numbers.
LCM from GCD
lcm(a, b) = a // gcd(a, b) * b. Divide before multiplying to reduce the risk of overflow in languages with fixed-size integers. For a list, fold: lcm of the first two, then with the third, and so on.
Typical interview problems
1. Simplify a fraction: divide numerator and denominator by their gcd, and normalize the sign so the denominator is positive.
2. Fraction addition and subtraction: for a/b + c/d, the result is (a*d + c*b) / (b*d), then simplify. For a long expression like "-1/2+1/3-1/6", parse each term and keep a running numerator and denominator.
3. GCD of strings: the largest string x that divides both s and t. If s + t != t + s, there is no answer; otherwise the answer is the prefix of length gcd(len(s), len(t)). This is a favorite because it looks like a string problem but is solved with gcd.
4. Water jug problem: with jugs of capacity x and y, you can measure z liters if and only if z <= x + y and z is a multiple of gcd(x, y) (Bezout's identity).
5. When do two events coincide? Buses every 12 and 18 minutes leave together again after lcm(12, 18) = 36 minutes.
6. Rotate an array by k using the juggling method: there are gcd(n, k) cycles to process.
7. Count lattice points on a segment from (x1, y1) to (x2, y2): gcd(|x2 - x1|, |y2 - y1|) + 1.
Extended Euclid
Sometimes you need integers x and y with a*x + b*y = gcd(a, b), for example to compute a modular inverse. The recursive version returns (g, x, y) and back-substitutes. Mention that in Python, pow(a, -1, m) computes the inverse directly when it exists.
Edge cases to mention
- gcd(0, 0) is usually defined as 0; handle it explicitly.
- Negative numbers: work with absolute values and fix signs at the end.
- Very large products: in Java or C++, use long and divide first.
How to present it
State the identity, write the iterative function, give the complexity, and then show how it solves the specific problem. Interviewers like seeing that you recognize the gcd hidden inside an apparently unrelated question.
If math-heavy follow-ups make you freeze in a live round, Linkjob AI (https://linkjob.ai) gives real-time help during job interviews and technical interviews, helping you keep your explanation steady while you work through the details.