Problem

Given n numbers, find the greatest common denominator between them.. We have already seen: Find GCD of two numbers

Examples

Example 1

1
2
3

Input: [12, 15, 21]
Output: 3
Explanation: The GCD of 12, 15, and 21 is 3.

Example 2:

1
2
3

 Input: [24, 36, 48]
 Output: 12
 Explanation: The GCD of 24, 36, and 48 is 12.

Solution

Method 1 - Using GCD of 2 numbers

The Greatest Common Divisor (GCD) of three or more numbers can be found by repeatedly computing the GCD of pairs of numbers.

To find the GCD of multiple numbers, we can iteratively compute the GCD of pairs of numbers:

  1. Compute the GCD of the first two numbers.
  2. Use the result to compute the GCD with the next number.
  3. Continue until all numbers are processed.

For e.g. gcd between 3 numbers a, b, and c:

1
2
3

gcd(a, b, c) = gcd(gcd(a, b), c)
= gcd(a, gcd(b, c))
= gcd(gcd(a, c), b)

To compute the GCD of an array of elements, follow these steps:

1
2
3

ans = arr[0];
For i = 1 to n-1:
    ans = GCD(ans, arr[i]);

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

public class Solution {
    public int findGCD(int[] nums) {
        int ans = nums[0];
        for (int i = 1; i < nums.length; i++) {
            ans = gcd(ans, nums[i]);
            if (ans == 1) {
                break; // GCD can't be smaller than 1
            }
        }
        return ans;
    }

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

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums1 = {12, 15, 21};
        System.out.println(solution.findGCD(nums1)); // Output: 3

        int[] nums2 = {24, 36, 48};
        System.out.println(solution.findGCD(nums2)); // Output: 12
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def findGCD(self, nums: List[int]) -> int:
        def gcd(a: int, b: int) -> int:
            while b:
                a, b = b, a % b
            return a
        
        ans = nums[0]
        for num in nums[1:]:
            ans = gcd(ans, num)
            if ans == 1:
                break # GCD can't be smaller than 1
        return ans

# Example usage
sol = Solution()
print(sol.findGCD([12, 15, 21]))  # Output: 3
print(sol.findGCD([24, 36, 48]))  # Output: 12

Complexity

  • ⏰ Time complexity: O(n * log(min(a, b))) where n is the number of elements and a and b are numbers being processed.
  • 🧺 Space complexity: O(1) for the iterative approach, as it only uses a constant amount of extra space.