Jobs

Interviews

Discussions

Find Greatest Common Divisor of Array

Easy

Asked by:

21 views

Topics:

ArraysGreedy Algorithms

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.

Example 1:

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

Example 2:

Input: nums = [7,5,6,8,3]
Output: 1
Explanation:
The smallest number in nums is 3.
The largest number in nums is 8.
The greatest common divisor of 3 and 8 is 1.

Example 3:

Input: nums = [3,3]
Output: 3
Explanation:
The smallest number in nums is 3.
The largest number in nums is 3.
The greatest common divisor of 3 and 3 is 3.

Constraints:

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

Try coding it in LeetCode

Find Greatest Common Divisor of Array

Easy

Asked by:

21 views

Topics:

ArraysGreedy Algorithms

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.

Example 1:

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

Example 2:

Input: nums = [7,5,6,8,3]
Output: 1
Explanation:
The smallest number in nums is 3.
The largest number in nums is 8.
The greatest common divisor of 3 and 8 is 1.

Example 3:

Input: nums = [3,3]
Output: 3
Explanation:
The smallest number in nums is 3.
The largest number in nums is 3.
The greatest common divisor of 3 and 3 is 3.

Constraints:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the input array?
Can the input array be empty or contain null?
What should I return if all the numbers in the array are zero?
Are all the input values guaranteed to be integers, or could they be floating-point numbers?
Is the order of numbers in the array significant?

Brute Force Solution

Approach

The brute force approach to finding the greatest common divisor (GCD) of a group of numbers involves checking every possible number to see if it divides all the numbers in the group evenly. We start with the smallest possible GCD and work our way up, testing each one. The largest number that divides all of them evenly is the GCD.

Here's how the algorithm would work step-by-step:

Find the smallest number in the group.
Start with the number one. We'll call this our test number.
See if the test number divides evenly into every number in the group. If any number leaves a remainder, it doesn't work, and we move on.
If the test number divides evenly into every number, remember it as a possible answer.
Increase the test number by one.
Repeat the process of checking if the test number divides evenly into all the numbers in the group.
Continue until the test number is equal to the smallest number we found at the very beginning.
The last test number that successfully divided all the numbers evenly is the greatest common divisor.

Code Implementation

def find_greatest_common_divisor_of_array(numbers):
    smallest_number = min(numbers)
    test_number = 1
    greatest_common_divisor = 1

    while test_number <= smallest_number:
        is_common_divisor = True

        # Check if the test number divides all numbers evenly
        for number in numbers:
            if number % test_number != 0:
                is_common_divisor = False
               break

        #If the number is a common divisor update greatest_common_divisor
        if is_common_divisor:
            greatest_common_divisor = test_number

        test_number += 1

    #Return the largest number found that divided all numbers
    return greatest_common_divisor

Big(O) Analysis

Time Complexity

O(n * minVal) – The provided solution iterates from 1 up to the smallest value (minVal) in the input array of size n. For each value in that range, it iterates through all n numbers in the array to check for divisibility. Therefore, the outer loop runs minVal times, and the inner loop runs n times. Thus, the time complexity is O(n * minVal), where minVal is the minimum value in the input array.

Space Complexity

O(1) – The provided algorithm uses a constant amount of extra space. It only stores a single variable to keep track of the 'test number' and does not create any auxiliary data structures like arrays or hash maps that scale with the input size N, where N is the number of elements in the input array. Therefore, the space complexity remains constant regardless of the size of the input array. No recursion is used, eliminating recursion stack space. Thus the space complexity is O(1).

Optimal Solution

Approach

To efficiently find the greatest common divisor of a collection of numbers, we avoid checking every possible divisor. The key is to find the GCD of pairs of numbers, progressively reducing the problem to a simpler form using the Euclidean algorithm.

Here's how the algorithm would work step-by-step:

Find the greatest common divisor of the first two numbers in the collection.
Take the result from the previous step and find the greatest common divisor of it and the next number in the collection.
Repeat this process, always finding the greatest common divisor between the previous result and the next number in the collection, until you have processed all the numbers.
The final result will be the greatest common divisor of all the numbers in the original collection.

Code Implementation

def find_greatest_common_divisor_of_array(number_collection):
    def find_greatest_common_divisor(
        first_number, second_number
    ):
        while(second_number):
            first_number, second_number = \
                second_number, first_number % second_number
        return first_number

    # Handle empty array
    if not number_collection:
        return 0

    # Initialize greatest common divisor with the first number
    greatest_common_divisor = number_collection[0]

    # Iterate to progressively find GCD
    for index in range(1, len(number_collection)):
        # Compute GCD between current GCD and the next number
        greatest_common_divisor = find_greatest_common_divisor(
            greatest_common_divisor,
            number_collection[index]
        )

    # Return the final GCD
    return greatest_common_divisor

Big(O) Analysis

Time Complexity

O(n * log(max_value)) – The algorithm iterates through the array of n numbers, applying the Euclidean algorithm in each step. The Euclidean algorithm's time complexity is logarithmic, specifically O(log(a, b)), where a and b are the two numbers being processed. In the worst case, a and b are close to the maximum value in the input array, so we represent it as O(log(max_value)). Since we apply the Euclidean algorithm n-1 times, the overall time complexity becomes O(n * log(max_value)).

Space Complexity

O(1) – The algorithm iteratively calculates the GCD, updating a single result variable. The Euclidean algorithm within the GCD calculation uses a few temporary variables, but their number is constant and independent of the input array's size, denoted as N. No additional data structures like arrays or hash maps are created that scale with the input size. Therefore, the auxiliary space used remains constant regardless of the input array size, leading to a space complexity of O(1).

Edge Cases

Case	How to Handle
Empty or null array	Return 0 or throw an exception, depending on the requirements, since the GCD is undefined for an empty set.
Array with a single element	Return the single element as the GCD since GCD(x) = x.
Array containing zero	Ignore zero elements as GCD(a, 0) = a; the GCD of the remaining elements can be computed.
Array containing negative numbers	Take the absolute value of each number, as GCD(a, b) = GCD(\|a\|, \|b\|).
Array with all identical numbers	The GCD is simply that number.
Array with very large numbers (potential integer overflow)	Use a data type that supports large integers (e.g., long in Java/C++, bigint in Python) to prevent overflow during GCD computation.
Array where all numbers are powers of the smallest number	The smallest number will be the GCD.
Array with extremely large size	Ensure the algorithm used (e.g., Euclidean algorithm) is efficient and avoids unnecessary memory allocation.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the input array?
Can the input array be empty or contain null?
What should I return if all the numbers in the array are zero?
Are all the input values guaranteed to be integers, or could they be floating-point numbers?
Is the order of numbers in the array significant?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Find the smallest number in the group.
Start with the number one. We'll call this our test number.
See if the test number divides evenly into every number in the group. If any number leaves a remainder, it doesn't work, and we move on.
If the test number divides evenly into every number, remember it as a possible answer.
Increase the test number by one.
Repeat the process of checking if the test number divides evenly into all the numbers in the group.
Continue until the test number is equal to the smallest number we found at the very beginning.
The last test number that successfully divided all the numbers evenly is the greatest common divisor.

Code Implementation

def find_greatest_common_divisor_of_array(numbers):
    smallest_number = min(numbers)
    test_number = 1
    greatest_common_divisor = 1

    while test_number <= smallest_number:
        is_common_divisor = True

        # Check if the test number divides all numbers evenly
        for number in numbers:
            if number % test_number != 0:
                is_common_divisor = False
               break

        #If the number is a common divisor update greatest_common_divisor
        if is_common_divisor:
            greatest_common_divisor = test_number

        test_number += 1

    #Return the largest number found that divided all numbers
    return greatest_common_divisor

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Find the greatest common divisor of the first two numbers in the collection.
Take the result from the previous step and find the greatest common divisor of it and the next number in the collection.
Repeat this process, always finding the greatest common divisor between the previous result and the next number in the collection, until you have processed all the numbers.
The final result will be the greatest common divisor of all the numbers in the original collection.

Code Implementation

def find_greatest_common_divisor_of_array(number_collection):
    def find_greatest_common_divisor(
        first_number, second_number
    ):
        while(second_number):
            first_number, second_number = \
                second_number, first_number % second_number
        return first_number

    # Handle empty array
    if not number_collection:
        return 0

    # Initialize greatest common divisor with the first number
    greatest_common_divisor = number_collection[0]

    # Iterate to progressively find GCD
    for index in range(1, len(number_collection)):
        # Compute GCD between current GCD and the next number
        greatest_common_divisor = find_greatest_common_divisor(
            greatest_common_divisor,
            number_collection[index]
        )

    # Return the final GCD
    return greatest_common_divisor

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null array	Return 0 or throw an exception, depending on the requirements, since the GCD is undefined for an empty set.
Array with a single element	Return the single element as the GCD since GCD(x) = x.
Array containing zero	Ignore zero elements as GCD(a, 0) = a; the GCD of the remaining elements can be computed.
Array containing negative numbers	Take the absolute value of each number, as GCD(a, b) = GCD(\|a\|, \|b\|).
Array with all identical numbers	The GCD is simply that number.
Array with very large numbers (potential integer overflow)	Use a data type that supports large integers (e.g., long in Java/C++, bigint in Python) to prevent overflow during GCD computation.
Array where all numbers are powers of the smallest number	The smallest number will be the GCD.
Array with extremely large size	Ensure the algorithm used (e.g., Euclidean algorithm) is efficient and avoids unnecessary memory allocation.