Skip to main content

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(NlogN)O(N logN)
  • Expected Auxiliary Space: O(1)O(1)

Constraints:​

  • 1≤N,arr[i]≤1051 ≤ 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(NlogN)O(N logN)
  • Auxiliary Space: O(1)O(1)