Greatest common divisor
Find the greatest common divisor of two integers, treating negative inputs as their absolute values.
Course progress
Problem 17 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
first = 84; second = 30
Expected output
6
What is happening?
Euclid's remainders are 84 mod 30 = 24, 30 mod 24 = 6, and 24 mod 6 = 0. The last non-zero divisor is 6.
Solution strategy
Build the right mental model
Use Euclid's algorithm: replace the pair with the second value and the remainder until the remainder becomes zero.
Core concepts
Euclidean algorithm · modulo
Complexity
Time O(log min(a, b)), space O(1).
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for greatest-common-divisor
using System;
class Program
{
static long GreatestCommonDivisor(int first, int second)
{
long a = Math.Abs((long)first);
long b = Math.Abs((long)second);
while (b != 0)
{
long remainder = a % b;
a = b;
b = remainder;
}
return a;
}
static void Main()
{
Console.WriteLine(GreatestCommonDivisor(84, 30));
}
}Knowledge check
Questions students often ask
What is the main idea behind greatest common divisor?
Use Euclid's algorithm: replace the pair with the second value and the remainder until the remainder becomes zero.
What is the time and space complexity of this solution?
Time O(log min(a, b)), space O(1).
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.