algoadvance

Leetcode 1979. Find Greatest Common Divisor of Array

Problem Statement

LeetCode Problem 1979: “Find Greatest Common Divisor of Array” requires you to write a function that returns the greatest common divisor (GCD) of the smallest and largest numbers in an array of integers.

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

Example:

Input: nums = [2,5,6,9,10]
Output: 2
Explanation: The smallest number is 2 and the largest number is 10. The greatest common divisor of 2 and 10 is 2.

Constraints:

Clarifying Questions

  1. Q: Can we use built-in functions to calculate GCD? A: Yes, you can use built-in functions if the language provides them.

  2. Q: Will the array always contain at least two elements? A: Yes, as per the constraints 2 <= nums.length.

  3. Q: Can elements in the array be negative? A: No, as per the constraints 1 <= nums[i].

Strategy

  1. Identifying the smallest and largest elements: Use the built-in Java Collections utility or a simple loop to find the minimum and maximum values in the array.

  2. Calculating the GCD: Use the Euclidean algorithm to find the GCD of the smallest and largest number.

Steps:

  1. Traverse the array to find the smallest and largest numbers.
  2. Implement the GCD function using the Euclidean algorithm.
  3. Return the computed GCD.

Code

public class Solution {
    public int findGCD(int[] nums) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        
        for (int num : nums) {
            if (num < min) {
                min = num;
            }
            if (num > max) {
                max = num;
            }
        }

        return gcd(min, max);
    }
    
    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 sol = new Solution();
        int[] nums = {2, 5, 6, 9, 10};
        System.out.println(sol.findGCD(nums)); // Output: 2
    }
}

Time Complexity

  1. Finding Min and Max: (O(n)), where (n) is the length of the array.
  2. GCD Calculation: The Euclidean algorithm takes (O(\log(\min(a, b)))) time in the worst case.

Overall Time Complexity: (O(n)) + (O(\log(\min(a, b)))). In this problem, the major time complexity is (O(n)) due to the array traversal, as it dominates the logarithmic part.

Space Complexity: (O(1)), as we are using a constant amount of extra space.

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