Problem Statement

You are given two integers n1 and n2. You need find the Greatest Common Divisor (GCD) of the two given numbers. Return the GCD of the two numbers.

The Greatest Common Divisor (GCD) of two integers is the largest positive integer that divides both of the integers.

Examples

Example 1:

Input: n1 = 4, n2 = 6
Output: 2

Explanation:
Divisors of n1 = 1, 2, 4
Divisors of n2 = 1, 2, 3, 6
Greatest Common Divisor = 2

Example 2:

Input: n1 = 7, n2 = 3
Output: 1

Explanation:
Divisors of n1 = 1, 7
Divisors of n2 = 1, 3
Greatest Common Divisor = 1

Approaches

1️⃣ Brute Force Approach

Intuition:

The GCD (Greatest Common Divisor), also known as HCF (Highest Common Factor), of two numbers is the largest number that divides both without leaving a remainder. To find the GCD, check all numbers from 1 up to the smaller of the two input numbers for common factors. The largest of these common factors is the GCD.

Approach:

1. Initialize a variable gcd with 1 that will store the greatest common divisor of the two given numbers.
2. Iterate from 1 to the minimum of the two numbers using a loop variable. Update the gcd if both the given numbers are divisible by the current value of the loop variable.
3. After the iterations are over, the greatest common divisor will be stored in the gcd variable.

Dry Run:

Initialization:

N1 = 4
N2 = 6
gcd = 1

First Iteration:

i = 1
N1 % i == 0 && N2 % i == 0
4 % 1 == 0 && 6 % 1 == 0
True

gcd = 1 (unchanged)

Second Iteration:

i = 2
N1 % i == 0 && N2 % i == 0
4 % 2 == 0 && 6 % 2 == 0
True

gcd = 2 (changed)

Third Iteration:

i = 3
N1 % i == 0 && N2 % i == 0
4 % 3 == 0 && 6 % 2 == 0
1 == 0 && 0 == 0
False

gcd = 2 (unchanged)

Fourth Pass:

i = 4
N1 % i == 0 && N2 % i == 0
4 % 4 == 0 && 6 % 4 == 0
0 == 0 && 0 == 2
False

gcd = 2 (unchanged)

Loop Termination:

i has become 5 which is larger than minimum of (4, 6)
So, Loop Terminated,
i = 5 > min(4, 6)

gcd = 2
return gcd

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to find the
    GCD of two numbers */
    int GCD(int n1, int n2) {
        
        // Variable to store the gcd
        int gcd = 1;
        
        // Iterate from 1 to min(n1, n2)
        for(int i = 1; i <= min(n1, n2); i++) {
            
            /* Check if i is a common
            divisor of both n1 and n2 */
            if(n1 % i == 0 && n2 % i == 0) {
                
                // Update gcd
                gcd = i;
            }
        }
        
        // Return stored GCD.
        return gcd;
    }
};

int main() {
    int n1 = 4, n2 = 6;
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to find the
    gcd of two numbers */
    int ans = sol.GCD(n1, n2);
    
    cout << "GCD of " << n1 << " and " << n2 << " is: " << ans << endl;
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(min(N1, N2)) – where N1 and N2 are given numbers. Iterating from 1 to min(N1, N2) and performing constant time operations in each iteration.
• Space Complexity:O(1) – Using a couple of variables i.e., constant space.

2️⃣ Backward Loop

Intuition:

The time complexity of the previous approach can be optimized if we iterate backward from min(n1, n2) to 1. This way the first divisor that is found for both numbers can be returned as the greatest common divisor of the numbers saving unnecessary iterations.

Approach:

1. Declare a variable gcd that will store the greatest common divisor of the two given numbers.
2. Iterate from the minimum of the two numbers down to 1 using a loop variable. Update the gcd if both the given numbers are divisible by the current value of the loop variable and break out from the loop to save unnecessary iterations.
3. The greatest common divisor for the two numbers is stored in the gcd variable which can be returned as the answer.

Dry Run:

Initially:

Initially
N1 = 4
N2 = 6
gcd = 1

First Iteration:

i = 4 (miniumum of N1 and N2)
	N1 % i == 0 && N2 % i == 0
	4 % 4 == 0 && 6 % 4 == 0
	False
	gcd = 1, Unchanged

Decrement i by 1

Second Iteration:

i = 3
	N1 % i == 0 && N2 % i == 0
	4 % 3 == 0 && 6 % 3 == 0
	False
	gcd = 1, Unchanged

Decrement i by 1

Third Iteration:

i = 2
	N1 % i == 0 && N2 % i == 0
	4 % 2 == 0 && 6 % 2 == 0
	True
	gcd = 2

Terminate the loop here and return the gcd

Code:

int GCD(int n1, int n2) {
        
        // Variable to store the gcd
        int gcd;
        
        // Iterate from 1 to min(n1, n2)
        for(int i = min(n1, n2); i >= 1; --i) {
            
            /* Check if i is a common
            divisor of both n1 and n2 */
            if(n1 % i == 0 && n2 % i == 0) {
                
                // Update gcd
                gcd = i;
                // Break to skip unnecessary iterations
                break;
            }
        }
        
        // Return stored GCD.
        return gcd;
    }

Complexity Analysis:

• Time Complexity:O(min(N1, N2)) – where N1 and N2 are given numbers. In the worst case, finding GCD will require iterating from min(N1, N2) till 1 and performing constant time operations in each iteration.
• Space Complexity:O(1) – Using a couple of variables i.e., constant space.

3️⃣ Optimal Approach

Intuition:

We can make use of the Euclid's Algorithm.

Euclid's Algorithm:

The algorithm is based on the principle that the GCD of two numbers a and b is the same as the GCD of b and a % b. We keep reducing the problem size by replacing a with b and b with a % b until b becomes 0. At this point, a will be the GCD.

Formula:

gcd(a, b) = gcd(b, a % b)

When b = 0, a is the GCD.

Approach:

1. Initialize a while loop till both numbers are greater than zero.
2. In each iteration perform the modulus operation of the greater number with the smaller number.
3. Once the loop terminates, one of the two variables stores a non-zero value which is the GCD for the given pair of numbers.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to find the
    GCD of two numbers*/
    int GCD(int n1, int n2) {
        
        /* Continue loop as long as both 
         n1 and n2 are greater than zero */
        while(n1 > 0 && n2 > 0) {
            
            /* If n1 is greater than n2, perform
             modulo operation - n1 % n2 */
            if(n1 > n2) {
                n1 = n1 % n2;
            }
            
            /* Else perform modulo
            operation - n2 % n1 */
            else {
                n2 = n2 % n1;
            }
        }
        
        // If n1 is zero, GCD is stored in n2
        if(n1 == 0) return n2;
        
        //else GCD is stored in n1
        return n1;
    }
};

int main() {
    int n1 = 4, n2 = 6;
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to find the
    gcd of two numbes */
    int ans = sol.GCD(n1, n2);
    
    cout << "GCD of " << n1 << " and " << n2 << " is: " << ans << endl;
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(log(min(N1, N2))) – where N1 and N2 are given numbers. Because in every iteration, the algorithm is dividing larger number with the smaller number resulting in time complexity.(approx.)
• Space Complexity:O(1) – Using a couple of variables i.e., constant space.