GCD of Array

Problem

Given an array of N positive integers, find GCD of all the array elements.

Examples:

Example 1:

Input: N = 3, arr[] = {2, 4, 6}
Output: 2
Explanation: GCD of 2,4,6 is 2.

Example 2:

Input: N = 1, arr[] = {1}
Output: 1
Explanation: Greatest common divisor of all the numbers is 1.

Your task:

You don't need to read input or print anything. Complete the function gcd() which takes N and array as input parameters and returns the gcd.

• Expected Time Complexity: $O(N logN)$
• Expected Auxiliary Space: $O(1)$

Constraints:

• $1 ≤ N, arr[i] ≤ 10^5$

Solution

Python

def gcd(self, n, arr):
    def compute_gcd(a, b):
        while b != 0:
            a, b = b, a % b
        return a
    if n == 1:
        return arr[0]
    current_gcd = arr[0]
    for i in range(1, n):
        current_gcd = compute_gcd(current_gcd, arr[i])
        if current_gcd == 1:  
            return 1
    return current_gcd 

Java

public int gcd(int N , int arr[]) { 
   if (N == 1) {
        return arr[0];
    }
    int currentGCD = arr[0];
    for (int i = 1; i < N; i++) {
        currentGCD = computeGCD(currentGCD, arr[i]);
        if (currentGCD == 1) {
            return 1;
        }
    }
    return currentGCD;
} 

private int computeGCD(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

C++

int gcd(int N, int arr[]) {
    if (N == 1) {
        return arr[0];
    }
    int currentGCD = arr[0];
    for (int i = 1; i < N; i++) {
        currentGCD = computeGCD(currentGCD, arr[i]);
        if (currentGCD == 1) {
            return 1;
        }
    }
    return currentGCD;
}

int computeGCD(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

C

int gcd(int N, int arr[]) {
    if (N == 1) {
        return arr[0];
    }
    int currentGCD = arr[0];
    for (int i = 1; i < N; i++) {
        currentGCD = computeGCD(currentGCD, arr[i]);
        if (currentGCD == 1) {
            return 1;
        }
    }
    return currentGCD;
}

int computeGCD(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

• Time Complexity: $O(N logN)$
• Auxiliary Space: $O(1)$