How do you compute the GCD of two numbers? | Interview Question

Q: How do you compute the GCD of two numbers?

**Target Audience:** Developers preparing for coding interviews who know loops and the modulo operator in Python; the math is explained from scratch. **Difficulty:** Easy **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First You are tiling a floor that measures 48 by 18 units and you want the **biggest square tiles** that cover it exactly, with no cutting. Try 18 by 18 tiles first: two fit along the 48 side, and a strip of 12 by 18 is left over. That strip is a smaller version of the same puzzle, so tile it with 12 by 12 squares: one fits, and a 12 by 6 strip is left. Two 6 by 6 squ

The problem

Question presented to candidate: "Write a Python function that returns the greatest common divisor of two integers. Explain why your method is correct and how fast it is, and tell me how you would get the least common multiple."

What a strong answer should cover:

The brute-force idea (try every divisor, O(min(a, b))) and why Euclid is better.
Euclid's algorithm gcd(a, b) = gcd(b, a % b) with base case gcd(a, 0) = a, and the reason: common divisors of (a, b) and (b, a mod b) are the same.
O(log min(a, b)) steps, worst case consecutive Fibonacci numbers; iterative O(1) space vs recursive O(log n) stack.
LCM as a // gcd(a, b) * b (divide first), and zero/negative inputs.
Python details: math.gcd and math.lcm (both accept any number of arguments since Python 3.9), the tuple swap a, b = b, a % b, % takes the sign of the divisor, and ints never overflow.

Clarifying questions expected:

Can inputs be negative or zero?
Is the LCM needed as well?

Code / implementation expected: Yes — an iterative Euclid in Python 3, then a mention of math.gcd.

math
gcd

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Developers preparing for coding interviews who know loops and the modulo operator in Python; the math is explained from scratch.
Difficulty: Easy
Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output you see in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

You are tiling a floor that measures 48 by 18 units and you want the biggest square tiles that cover it exactly, with no cutting. Try 18 by 18 tiles first: two fit along the 48 side, and a strip of 12 by 18 is left over. That strip is a smaller version of the

The solution is hidden so you can try first

7 min read · 13 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonEuclid with step counts, LCM and a trace

Practice

PythonSubtraction vs modulo, Fibonacci worst case, lcm(1..k)

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.