How Do You Find The GCD of Two Numbers?

Different Approaches to Look Out For

Given two non-negative integers a & b. Find the GCD (greatest common divisor), i.e., the largest number which is a divisor of both a & b. It’s commonly denoted by gcd(a,b).

Ready to dive in?

Problem Statement

Examples-  Input: a=32, b=20  Output: 4  Explanation: 4 is the largest factor that divides both of the numbers.

Explore more examples for a better understanding

From min(A, B) to 1, we can traverse over all the numbers and determine if the current number divides both A & B or not. If it does, then it will be the GCD of A and B.

Want to see code implementation?

Approach 1: Simple Approach

Time complexity: O(min(A, B)) Space complexity: O(1)

Want to explore other approaches?

Subtract smaller numbers from larger ones when we want to reduce larger numbers. It does not change GCD. Alternatively, we can divide the smaller number & the algorithm stops when the remainder=0.

Want to see code implementation?

Approach 2: Euclid’s Algorithm

Time complexity: O(Log min(a, b)).  Space complexity: O(1)

Want to see code implementation?

Start your journey now and learn how to determine the GCD of two numbers with code implementation.

Ready to level up your coding skills?

Step Up Your Game with InterviewBit Web Stories

Don't miss out on the chance to upskill yourself with IntervewBit's engaging web stories. 

“