Split The Array To Make Coprime Products - Leetcode Solution

Problem Statement:

Given an array nums[] of size n, you need to split it into two non-empty subarrays, say left and right, such that the product of the elements in the left subarray is coprime with the product of the elements in the right subarray. You need to return the length of the smallest left subarray.

If it is not possible to split the array as described above, return -1.

Solution:

To approach this problem, we need to understand what coprime means. Two numbers a and b are called coprime if gcd(a, b) = 1, where gcd(a, b) denotes the greatest common divisor of a and b.

With this in mind, let us consider the given array and try to split it into two subarrays such that the product of the elements in the left subarray is coprime with the product of the elements in the right subarray.

Let us first find the product of all the elements in the array. Let this be denoted by prod. We can then iterate through the array and for each element a[i], we can calculate the gcd of prod and a[i]. If the gcd is 1, then we have found a subarray that satisfies the required condition. Otherwise, we can continue iterating through the array.

In order to find the gcd of prod and a[i], we can make use of the fact that gcd(a, b) = gcd(b, a % b), where % denotes the modulo operator. Thus, we can use this property to calculate the gcd of prod and a[i] in an efficient manner.

Let us now consider the case when it is not possible to split the array as described above. In this case, we can return -1 as required by the problem statement.

Finally, we need to return the length of the smallest left subarray that satisfies the required condition. We can keep track of the length of the smallest left subarray found so far and update it as required.

Algorithm:

1. Calculate the product of all the elements in the array.
2. Iterate through the array and for each element a[i], calculate the gcd of prod and a[i].
3. If the gcd is 1, we have found a subarray that satisfies the required condition. Update the length of the smallest left subarray found so far.
4. If it is not possible to split the array as described above, return -1.
5. Return the length of the smallest left subarray found so far.

Code:

Here is the code for the above algorithm in Python:

def splitArray(nums):
    n = len(nums)
    prod = 1
    for i in range(n):
        prod *= nums[i]
    
    left_len = n
    right_prod = prod
    left_prod = 1
    
    for i in range(n):
        left_prod *= nums[i]
        right_prod //= nums[i]
        
        gcd_val = gcd(left_prod, right_prod)
        if gcd_val == 1:
            left_len = i + 1
            break
        
    if left_len == n:
        return -1
    else:
        return left_len
    
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

Time Complexity:

The time complexity of the above algorithm is O(n log m), where n is the length of the array and m is the maximum value in the array.

Space Complexity:

The space complexity of the above algorithm is O(1), since we are using only constant extra space.

Overall, this algorithm provides a fast and efficient solution to the given problem.

1