We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Greatest Common Divisor of Array

Number: 2106

Difficulty: Easy

Paid? No

Companies: TIAA

Problem Description

Given an integer array, determine the greatest common divisor (GCD) of the smallest and largest numbers in the array. The GCD is the largest positive integer that evenly divides both numbers.

Key Insights

  • Find the minimum and maximum values in the array.
  • Apply the Euclidean algorithm to compute the GCD of these two numbers.
  • The Euclidean algorithm works by repeatedly replacing the larger number by the remainder when it is divided by the smaller number until the remainder is zero.

Space and Time Complexity

Time Complexity: O(n) for scanning the array plus O(log(min)) for the Euclidean algorithm, which overall is O(n). Space Complexity: O(1) as only a few variables are used.

Solution

The solution involves two main steps:

  1. Traverse the array to identify the smallest and largest numbers.
  2. Compute the GCD of these two numbers using the Euclidean algorithm. Data structures used include basic variables for tracking minimum and maximum values. The main algorithmic approach is simple iteration for the array scan and the use of a loop (or recursion) for the Euclidean algorithm.

Code Solutions

# Function to compute GCD using Euclidean algorithm
def gcd(a, b):
    # Continue until b becomes 0
    while b:
        # Update a and b for next iteration
        a, b = b, a % b
    return a

def findGCD(nums):
    # Find minimum and maximum elements in the array
    smallest = min(nums)
    largest = max(nums)
    # Return the GCD of the smallest and largest numbers
    return gcd(smallest, largest)

# Example usage:
# nums = [2, 5, 6, 9, 10]
# print(findGCD(nums))  # Output: 2
← Back to All Questions