Split the Array to Make Coprime Products

Problem Description

You are given a 0-indexed integer array nums of length n. A split at an index i where 0 <= i <= n - 2 is called valid if the product of the first i + 1 elements and the product of the remaining elements are coprime. Return the smallest index i at which the array can be split validly or -1 if there is no such split.

Key Insights

• Two values are coprime if their greatest common divisor (GCD) is 1.
• We need to compute the prefix product and the suffix product for each possible split.
• A valid split is identified when the GCD of the prefix product and the suffix product is 1.
• Efficient computation is necessary due to the constraints on the size of the array and the values.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can utilize a prefix product to calculate the product of elements up to each index i, and a suffix product to calculate the product of elements from index i + 1 to the end of the array. The algorithm proceeds as follows:

1. Initialize a variable to keep track of the prefix product.
2. Calculate the total product of the array.
3. For each index i from 0 to n - 2, update the prefix product and compute the suffix product as total_product / prefix_product.
4. Check if the GCD of the prefix product and the suffix product is 1 to determine if the split is valid.
5. Return the first valid index found, or -1 if no valid split exists.

Code Solutions