#2584
Split the Array to Make Coprime Products
international master · 2035 · lc hard +32 · verified · 28.7% accepted · 321 likes · top 6%
Description
A split at index i (where 0 <= i <= n - 2) of a 0-indexed array nums is valid if the product of nums[0..i] and the product of nums[i+1..n-1] are coprime (GCD equals 1). Return the smallest valid split index, or -1 if none exists.
Example 1:
Input: nums = [4,7,8,15,3,5]
Output: 2
Explanation: The table above shows the values of the product of the first i + 1 elements, the remaining elements, and their gcd at each index i.
The only valid split is at index 2.
Example 2:
Input: nums = [4,7,15,8,3,5]
Output: -1
Explanation: The table above shows the values of the product of the first i + 1 elements, the remaining elements, and their gcd at each index i.
There is no valid split.
Code
1
2
3