How to Find the GCD of N Integers Using Python

Calculate the Greatest Common Divisor (GCD) of N integers using Python, with efficient input handling and output formatting.

Understand the Problem

Problem Statement

In this article, we will explore a Python program to calculate the Greatest Common Divisor (GCD) of N integers. The GCD of two or more integers is the largest positive integer that divides each of the numbers without leaving a remainder.

This program is particularly useful in mathematical computations and competitive programming. Let’s dive into the problem, input/output format, and solution.

Constraints

1 ≤ N ≤ 100 (number of integers)
1 ≤ each integer ≤ 10⁹ (value of each integer)
All input values must be positive integers
Input must be provided as space-separated integers on the second line
The result must be a single integer representing the GCD

Examples

Example 1

Input

5
4 6 2 8 16

Output

Explanation

Divisors of 4: 1, 2, 4
Divisors of 6: 1, 2, 3, 6
Divisors of 2: 1, 2
Divisors of 8: 1, 2, 4, 8
Divisors of 16: 1, 2, 4, 8, 16

The common divisors are 1 and 2. The largest common divisor is 2, which is the output.

Example 2

Input

2
8 12

Output

Explanation

Divisors of 8: 1, 2, 4, 8
Divisors of 12: 1, 2, 3, 4, 6, 12

The common divisors are 1, 2, and 4. The largest common divisor is 4, which is the output.

Solution

#include <stdio.h>

// Function to calculate GCD of two numbers using Euclidean algorithm
int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

// Function to calculate GCD of an array of numbers
int gcd_of_array(int arr[], int n) {
    int result = arr[0];
    for (int i = 1; i < n; i++) {
        result = gcd(result, arr[i]);
        if (result == 1)
            return 1; // Early exit optimization
    }
    return result;
}

int main() {
    int n;
    printf("Enter the number of integers (N): ");
    scanf("%d", &n);
    
    int arr[n];
    printf("Enter the integers separated by space: ");
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    int result = gcd_of_array(arr, n);
    printf("The GCD of the given numbers is: %d\n", result);
    
    return 0;
}

Time:O(N * log(M)) where N is the number of integers and M is the maximum value among them

Space:O(1) excluding input array space

Approach:

Step-by-Step Explanation:

gcd() Function: Implements the Euclidean algorithm recursively. For two numbers a and b, it returns gcd(b, a % b) until b becomes 0.
gcd_of_array() Function: Iterates through the array, maintaining a running GCD result. It applies the two-number GCD function cumulatively.
Early Exit Optimization: If at any point the GCD becomes 1, the function returns immediately since the GCD of any number with 1 is always 1.
main() Function: Reads input, stores numbers in an array, calls the GCD function, and prints the result.

Visual Explanation

Loading diagram...

All Problems