Jobs

Interviews

Discussions

Check If It Is a Good Array

Hard

Dropbox

2 views

Topics:

ArraysGreedy Algorithms

Given an array nums of positive integers. Your task is to select some subset of nums, multiply each element by an integer and add all these numbers. The array is said to be good if you can obtain a sum of 1 from the array by any possible subset and multiplicand.

Return True if the array is good otherwise return False.

Example 1:

Input: nums = [12,5,7,23]
Output: true
Explanation: Pick numbers 5 and 7.
5*3 + 7*(-2) = 1

Example 2:

Input: nums = [29,6,10]
Output: true
Explanation: Pick numbers 29, 6 and 10.
29*1 + 6*(-3) + 10*(-1) = 1

Example 3:

Input: nums = [3,6]
Output: false

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9

Try coding it in LeetCode

Check If It Is a Good Array

Hard

Dropbox

2 views

Topics:

ArraysGreedy Algorithms

Return True if the array is good otherwise return False.

Example 1:

Input: nums = [12,5,7,23]
Output: true
Explanation: Pick numbers 5 and 7.
5*3 + 7*(-2) = 1

Example 2:

Input: nums = [29,6,10]
Output: true
Explanation: Pick numbers 29, 6 and 10.
29*1 + 6*(-3) + 10*(-1) = 1

Example 3:

Input: nums = [3,6]
Output: false

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9

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 `nums` array? Can they be negative, zero, or very large?
What is the maximum possible size of the `nums` array? This will help me consider potential performance implications.
If the input array is empty or null, what should I return? Should I throw an exception or return `false`?
Are there any constraints on the time complexity of the solution, or is the goal to find the most efficient solution possible?
Are duplicate numbers allowed in the `nums` array, and if so, how should they be handled in determining the GCD?

Brute Force Solution

Approach

To determine if a collection of numbers is 'good' using brute force, we'll explore all possible subsets. We check each subset to see if it satisfies a specific condition related to their greatest common divisor. If we find even one 'good' subset, we declare the entire collection 'good'.

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

First, consider a group containing only the first number.
Then, consider all groups containing the first two numbers: just the first number, just the second number, or both numbers together.
Continue this process, each time including the next number in all possible combinations with the previous numbers.
For each of these groups, calculate their greatest common divisor using a simple method such as repeatedly finding remainders.
If any of these groups has a greatest common divisor of 1, then the entire collection is considered 'good'.
If we have checked every possible group of numbers, from smallest to largest, and none have a greatest common divisor of 1, the entire collection is 'not good'.

Code Implementation

def check_if_good_array_brute_force(numbers):
    number_of_elements = len(numbers)

    for i in range(1, 1 << number_of_elements):
        subset = []
        for j in range(number_of_elements):
            if (i >> j) & 1:
                subset.append(numbers[j])

        # Calculate the greatest common divisor of the current subset.
        current_greatest_common_divisor = subset[0]

        for k in range(1, len(subset)):
            current_greatest_common_divisor = find_gcd(
                current_greatest_common_divisor, subset[k]
            )

        # If GCD is 1, the array is good.
        if current_greatest_common_divisor == 1:
            return True

    return False

def find_gcd(first_number, second_number):
    #Euclid's algorithm.
    while(second_number):
        first_number, second_number = second_number, first_number % second_number

    return first_number

Big(O) Analysis

Time Complexity

O(n * 2^n) – The algorithm iterates through all possible subsets of the input array of size n. Generating all subsets requires 2^n operations. For each subset, it calculates the greatest common divisor (GCD). Calculating the GCD of a subset can take at most O(n) time in the worst-case scenario where all numbers in the array need to be factored down. Therefore, the overall time complexity becomes O(n * 2^n) since we calculate the GCD for each of the 2^n subsets which each can potentially cost O(n) time.

Space Complexity

O(1) – The algorithm described iterates through subsets and calculates the greatest common divisor (GCD) for each. While it explores all possible subsets, it doesn't explicitly store all the subsets simultaneously. The GCD calculation itself requires a constant amount of extra space for temporary variables during the computation. Therefore, the auxiliary space used is independent of the input array's size (N), making it constant space.

Optimal Solution

Approach

The key insight is that a set of numbers is 'good' if their greatest common divisor (GCD) is one. We can use a property of GCDs to solve this efficiently without checking all possible subsets.

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

Find the greatest common divisor (GCD) of all the numbers in the set.
If the GCD is one, then the set is 'good'.
Otherwise (if the GCD is not one), the set is not 'good'.

Code Implementation

def check_if_good_array(numbers):

    def greatest_common_divisor(first_number, second_number):
        while(second_number):
            first_number, second_number = second_number, first_number % second_number
        return first_number

    # Calculate the GCD of all numbers
    result_gcd = numbers[0]

    for i in range(1, len(numbers)):
        # Update GCD with the next number
        result_gcd = greatest_common_divisor(result_gcd, numbers[i])

    #If GCD is 1, then the array is good
    if result_gcd == 1:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

O(n * log(MAX)) – The algorithm calculates the greatest common divisor (GCD) of all numbers in the input array. The GCD function typically has a time complexity of O(log(min(a, b))), where a and b are the two numbers being processed. In the worst-case scenario, we compute GCD for each element in the array, resulting in n GCD computations. The GCD calculation's cost is logarithmic with respect to the maximum value in the input array (MAX). Thus, the overall time complexity is O(n * log(MAX)).

Space Complexity

O(1) – The algorithm calculates the greatest common divisor (GCD) of the input array. The GCD calculation typically uses a recursive or iterative approach that involves storing a few integer variables for intermediate results, such as the current GCD value. The number of these variables remains constant regardless of the input array's size (N). Therefore, the auxiliary space used is constant.

Edge Cases

Case	How to Handle
Empty or null input array	Return false immediately as no subsequence can have a GCD of 1.
Input array with a single element	Return true if the single element is 1, otherwise return false.
Array contains only the number 1	Return true as the subsequence consisting of only the number 1 has a GCD of 1.
Array contains only multiples of a single prime number (e.g., only even numbers)	Return false as the GCD of any subsequence will be that prime number.
Array contains a large number of elements with a high range of values potentially leading to integer overflow during GCD calculations.	Use the appropriate data type to avoid overflow during GCD calculations or handle overflow cases gracefully.
Array with a mix of very small and very large numbers.	The GCD algorithm should handle these values correctly, potentially using optimization techniques to avoid unnecessary calculations.
Array where the GCD of all elements is greater than 1.	The solution must be able to determine that no subsequence will have a GCD of 1, even if individual pairs of elements are coprime.
The array is very large (memory constraints).	The solution should avoid creating excessively large auxiliary data structures and aim for an efficient algorithm, potentially using an iterative approach instead of recursion.

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 `nums` array? Can they be negative, zero, or very large?
What is the maximum possible size of the `nums` array? This will help me consider potential performance implications.
If the input array is empty or null, what should I return? Should I throw an exception or return `false`?
Are there any constraints on the time complexity of the solution, or is the goal to find the most efficient solution possible?
Are duplicate numbers allowed in the `nums` array, and if so, how should they be handled in determining the GCD?

Brute Force Solution

Approach

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

First, consider a group containing only the first number.
Then, consider all groups containing the first two numbers: just the first number, just the second number, or both numbers together.
Continue this process, each time including the next number in all possible combinations with the previous numbers.
For each of these groups, calculate their greatest common divisor using a simple method such as repeatedly finding remainders.
If any of these groups has a greatest common divisor of 1, then the entire collection is considered 'good'.
If we have checked every possible group of numbers, from smallest to largest, and none have a greatest common divisor of 1, the entire collection is 'not good'.

Code Implementation

def check_if_good_array_brute_force(numbers):
    number_of_elements = len(numbers)

    for i in range(1, 1 << number_of_elements):
        subset = []
        for j in range(number_of_elements):
            if (i >> j) & 1:
                subset.append(numbers[j])

        # Calculate the greatest common divisor of the current subset.
        current_greatest_common_divisor = subset[0]

        for k in range(1, len(subset)):
            current_greatest_common_divisor = find_gcd(
                current_greatest_common_divisor, subset[k]
            )

        # If GCD is 1, the array is good.
        if current_greatest_common_divisor == 1:
            return True

    return False

def find_gcd(first_number, second_number):
    #Euclid's algorithm.
    while(second_number):
        first_number, second_number = second_number, first_number % second_number

    return first_number

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The key insight is that a set of numbers is 'good' if their greatest common divisor (GCD) is one. We can use a property of GCDs to solve this efficiently without checking all possible subsets.

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

Find the greatest common divisor (GCD) of all the numbers in the set.
If the GCD is one, then the set is 'good'.
Otherwise (if the GCD is not one), the set is not 'good'.

Code Implementation

def check_if_good_array(numbers):

    def greatest_common_divisor(first_number, second_number):
        while(second_number):
            first_number, second_number = second_number, first_number % second_number
        return first_number

    # Calculate the GCD of all numbers
    result_gcd = numbers[0]

    for i in range(1, len(numbers)):
        # Update GCD with the next number
        result_gcd = greatest_common_divisor(result_gcd, numbers[i])

    #If GCD is 1, then the array is good
    if result_gcd == 1:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return false immediately as no subsequence can have a GCD of 1.
Input array with a single element	Return true if the single element is 1, otherwise return false.
Array contains only the number 1	Return true as the subsequence consisting of only the number 1 has a GCD of 1.
Array contains only multiples of a single prime number (e.g., only even numbers)	Return false as the GCD of any subsequence will be that prime number.
Array contains a large number of elements with a high range of values potentially leading to integer overflow during GCD calculations.	Use the appropriate data type to avoid overflow during GCD calculations or handle overflow cases gracefully.
Array with a mix of very small and very large numbers.	The GCD algorithm should handle these values correctly, potentially using optimization techniques to avoid unnecessary calculations.
Array where the GCD of all elements is greater than 1.	The solution must be able to determine that no subsequence will have a GCD of 1, even if individual pairs of elements are coprime.
The array is very large (memory constraints).	The solution should avoid creating excessively large auxiliary data structures and aim for an efficient algorithm, potentially using an iterative approach instead of recursion.