DSA interview question

GCD of Two Numbers

Easy · Algorithms · Topics: basic maths, number theory, euclidean algorithm

The problem

A tiling app lets users cover an a × b floor with identical square tiles and wants the largest square tile that fits perfectly with no cutting. That's the Greatest Common Divisor (GCD) of the two sides. The same function is needed to simplify fractions and compute the least common multiple for scheduling repeating events. Checking every candidate divisor works but is far too slow for values up to 10^9; Euclid's algorithm, over 2,000 years old, solves it in a handful of steps.

Example: gcd(48, 180) = 12, so a 48 × 180 floor takes 12 × 12 tiles.

Function signature

long long gcd(long long a, long long b);  // greatest common divisor, a, b >= 0, not both 0
long long lcm(long long a, long long b);  // least common multiple, a, b > 0

Test cases

Input `(a, b)`	Output	Explanation
(12, 18)	6	Largest number dividing both
(48, 180)	12
(7, 13)	1	Coprime numbers
(100, 25)	25	One divides the other
(0, 5)	5	gcd(0, b) = b
(1, 1)	1
(1000000000, 999999999)	1	Consecutive integers are coprime; Euclid needs very few steps
lcm(4, 6)	12	lcm = a / gcd × b

(Confirm: inputs are non-negative and not both zero; values up to 10^9.)

How interviewers phrase it

"Find the GCD (HCF) of two numbers."
"Find the LCM of two numbers" (which needs the GCD).
As a building block: "Simplify a fraction," "Find the GCD of an array," or problems about gcd-based periodicity.

Clarifying questions to ask

Can the numbers be zero or negative?
What's the range? (Decides whether brute force is acceptable.)
Is the LCM also needed, and could it overflow?

Follow-ups to expect

"Why does gcd(a, b) = gcd(b, a % b) hold?"
"What's the complexity of Euclid's algorithm?"
"What about the brute-force approach?"
"How do you compute the LCM safely?"
"Is there a built-in?"
"GCD of an array?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview