algoadvance

Leetcode 1979. Find Greatest Common Divisor of Array

Problem Statement

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

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

Clarifying Questions

  1. What is the length range of the input array nums?
    • The length can range from 2 to 1000.
  2. What is the range of the numbers in the array nums?
    • The elements in nums can range from 1 to 1000.
  3. Can the array have duplicate elements?
    • Yes, the array can have duplicate elements, but this does not affect finding the minimum and maximum values.
  4. Can we assume that the input array is always valid and non-empty?
    • Yes, based on the problem constraints, we can assume the input array is always valid and non-empty.

Strategy

  1. Find the smallest and largest elements:
    • We’ll iterate through the array to identify the smallest and largest numbers.
  2. Compute the GCD of the smallest and largest elements:
    • We’ll use the Euclidean algorithm to compute the GCD. This algorithm is efficient and well-suited for our purpose.

Code

#include <iostream>
#include <vector>
#include <algorithm> // for std::min_element and std::max_element

// Function to compute the GCD using the Euclidean algorithm
int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int findGCD(const std::vector<int>& nums) {
    if (nums.empty()) return 0;

    // Find the smallest and largest elements in the array
    int min_elem = *std::min_element(nums.begin(), nums.end());
    int max_elem = *std::max_element(nums.begin(), nums.end());

    // Return the GCD of smallest and largest elements
    return gcd(min_elem, max_elem);
}

// Example usage
int main() {
    std::vector<int> nums = {2, 5, 6, 9, 10};
    std::cout << "GCD of smallest and largest elements: " << findGCD(nums) << std::endl;
    return 0;
}

Time Complexity

  1. Finding smallest and largest elements:
    • The time complexity to find the smallest and largest elements is ( O(n) ) where ( n ) is the number of elements in the array.
  2. Computing the GCD:
    • The Euclidean algorithm runs in ( O(\log(\min(a, b))) ) time, where ( a ) and ( b ) are the two numbers whose GCD we are calculating. Since in this problem, ( a ) and ( b ) can be at most 1000, the GCD calculation is very efficient.
  3. Overall Time Complexity:
    • The overall time complexity of our approach remains ( O(n) ), dominated by the time to find the smallest and largest elements in the array.

This efficient solution guarantees that we can handle the maximum constraints comfortably.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI