Find Greatest Common Divisor of Array - Practice Coding Problems

Find Greatest Common Divisor of Array - Problem

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

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

Input & Output

Example 1 — Basic Array

$ Input: nums = [2,5,6,9,10]

› Output: 2

💡 Note: The smallest number is 2, the largest is 10. GCD(2, 10) = 2 since 2 divides both 2 and 10 evenly.

Example 2 — Small Array

$ Input: nums = [7,5,6,8,3]

› Output: 1

💡 Note: The smallest number is 3, the largest is 8. GCD(3, 8) = 1 since they share no common divisors other than 1.

Example 3 — Two Elements

$ Input: nums = [3,3]

› Output: 3

💡 Note: Both minimum and maximum are 3. GCD(3, 3) = 3.

Constraints

2 ≤ nums.length ≤ 1000
1 ≤ nums[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array with various integers

Find Min/Max

Identify smallest and largest values

Calculate GCD

Return GCD of min and max values

Key Takeaway

🎯 Key Insight: Only the minimum and maximum elements matter for the GCD calculation

Asked in

G Google 12 M Microsoft 8 a Amazon 6

The key insight is that we only need the GCD of the minimum and maximum elements. Find min/max in O(n), then use Euclidean algorithm for efficient GCD calculation. Time: O(n + log(min(a,b))), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force GCD	O(n + min(a,b))	O(1)	Find min/max, then check all divisors from smaller number down to 1
Euclidean Algorithm	O(n + log(min(a,b)))	O(1)	Find min/max, then use efficient Euclidean algorithm for GCD

Brute Force GCD — Algorithm Steps

Find minimum and maximum values in array
Check divisors from min(a,b) down to 1
Return first divisor that divides both numbers

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Min/Max

Scan array to find smallest and largest values

Check Divisors

Test each number from smaller value down to 1

First Match

Return first number that divides both evenly

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize) {
    int minVal = nums[0];
    int maxVal = nums[0];
    
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] < minVal) minVal = nums[i];
        if (nums[i] > maxVal) maxVal = nums[i];
    }
    
    int smaller = (minVal < maxVal) ? minVal : maxVal;
    
    // Check all possible divisors from smaller number down to 1
    for (int i = smaller; i >= 1; i--) {
        if (minVal % i == 0 && maxVal % i == 0) {
            return i;
        }
    }
    
    return 1;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple array parsing
    int nums[1000];
    int size = 0;
    char* token = strtok(line, "[,]");
    
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n' && token[0] != ']') {
            nums[size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + min(a,b))

O(n) to find min/max, then O(min(a,b)) to check all divisors

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables for min, max, and loop counter

✓ Linear Space

23.0K Views

Medium Frequency

~10 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force GCD — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler