Find Greatest Common Divisor of Array

Easy
174.

Find Greatest Common Divisor of Array

Find Greatest Common Divisor of Array is an easy coding problem on arrays, math and number theory, asked in Amazon, TCS, Infosys and Accenture interviews.

Given an integer array nums, return the greatest common divisor of its smallest and largest elements.

The greatest common divisor of two numbers is the largest positive integer that divides both of them.

Example 1

Input
nums = [2,5,6,9,10]
Output
2
Explanation
The smallest is 2 and the largest is 10; gcd(2, 10) = 2.

Example 2

Input
nums = [7,5,6,8,3]
Output
1
Explanation
gcd(3, 8) = 1.

Example 3

Input
nums = [3,3]
Output
3

Constraints

  • 2 <= nums.length <= 40
  • 1 <= nums[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var findGCD = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find Greatest Common Divisor of Array — Problem & Solution

Find Greatest Common Divisor of Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Find Greatest Common Divisor of Array is an easy coding problem on arrays, math and number theory, asked in Amazon, TCS, Infosys and Accenture interviews.

Problem statement

Given an integer array nums, return the greatest common divisor of its smallest and largest elements.

The greatest common divisor of two numbers is the largest positive integer that divides both of them.

Example 1

Input: nums = [2,5,6,9,10]
Output: 2
Explanation: The smallest is 2 and the largest is 10; gcd(2, 10) = 2.

Example 2

Input: nums = [7,5,6,8,3]
Output: 1
Explanation: gcd(3, 8) = 1.

Example 3

Input: nums = [3,3]
Output: 3

Constraints

  • 2 <= nums.length <= 40
  • 1 <= nums[i] <= 1000

Hints for Find Greatest Common Divisor of Array

  1. Hint 1

    One pass finds both the minimum and the maximum.

  2. Hint 2

    Euclid's algorithm computes the gcd: gcd(a, b) = gcd(b, a mod b), ending when b reaches 0.

  3. Hint 3

    The smallest and largest may be the same element when every value is equal — that is fine, gcd(x, x) = x.

How to solve Find Greatest Common Divisor of Array

Find the minimum and maximum in one pass, then apply Euclid's algorithm to the pair.

Approach

  1. Compute a = min(nums), b = max(nums).
  2. While b != 0, set (a, b) = (b, a % b).
  3. Return a.

Why it works

Any common divisor of a and b also divides a mod b, and vice versa, so the gcd is preserved by each step while the second argument strictly shrinks to zero. The last non-zero value is the gcd.

Complexity

  • Time — O(n + log(max))
  • Space — O(1)

Pitfalls

  • When every element is equal, min and max coincide and gcd(x, x) = x.
  • Only the extreme elements matter — the gcd of the whole array is a different question.

Reference solution

Python

def findGCD(nums):
    a, b = min(nums), max(nums)
    while b:
        a, b = b, a % b
    return a

Java

public static int findGCD(int[] nums) {
    int lo = nums[0], hi = nums[0];
    for (int x : nums) {
        if (x < lo) lo = x;
        if (x > hi) hi = x;
    }
    while (lo != 0) {
        int t = hi % lo;
        hi = lo;
        lo = t;
    }
    return hi;
}

C++

int findGCD(vector<int>& nums) {
    int lo = nums[0], hi = nums[0];
    for (int x : nums) {
        if (x < lo) lo = x;
        if (x > hi) hi = x;
    }
    while (lo != 0) {
        int t = hi % lo;
        hi = lo;
        lo = t;
    }
    return hi;
}

JavaScript

var findGCD = function(nums) {
    let lo = nums[0], hi = nums[0];
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] < lo) lo = nums[i];
        if (nums[i] > hi) hi = nums[i];
    }
    while (lo !== 0) {
        const t = hi % lo;
        hi = lo;
        lo = t;
    }
    return hi;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays