2584. Split the Array to Make Coprime Products Hard

1/**
2 * [2584] Split the Array to Make Coprime Products
3 *
4 * You are given a 0-indexed integer array nums of length n.
5 * 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.
6 * 
7 * 	For example, if nums = [2, 3, 3], then a split at the index i = 0 is valid because 2 and 9 are coprime, while a split at the index i = 1 is not valid because 6 and 3 are not coprime. A split at the index i = 2 is not valid because i == n - 1.
8 * 
9 * Return the smallest index i at which the array can be split validly or -1 if there is no such split.
10 * Two values val1 and val2 are coprime if gcd(val1, val2) == 1 where gcd(val1, val2) is the greatest common divisor of val1 and val2.
11 *  
12 * Example 1:
13 * <img alt="" src="https://assets.leetcode.com/uploads/2022/12/14/second.PNG" style="width: 450px; height: 211px;" />
14 * Input: nums = [4,7,8,15,3,5]
15 * Output: 2
16 * 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.
17 * The only valid split is at index 2.
18 * 
19 * Example 2:
20 * <img alt="" src="https://assets.leetcode.com/uploads/2022/12/14/capture.PNG" style="width: 450px; height: 215px;" />
21 * Input: nums = [4,7,15,8,3,5]
22 * Output: -1
23 * 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.
24 * There is no valid split.
25 * 
26 *  
27 * Constraints:
28 * 
29 * 	n == nums.length
30 * 	1 <= n <= 10^4
31 * 	1 <= nums[i] <= 10^6
32 * 
33 */
34pub struct Solution {}
35
36// problem: https://leetcode.com/problems/split-the-array-to-make-coprime-products/
37// discuss: https://leetcode.com/problems/split-the-array-to-make-coprime-products/discuss/?currentPage=1&orderBy=most_votes&query=
38
39// submission codes start here
40
41impl Solution {
42    pub fn find_valid_split(nums: Vec<i32>) -> i32 {
43        0
44    }
45}
46
47// submission codes end
48
49#[cfg(test)]
50mod tests {
51    use super::*;
52
53    #[test]
54    fn test_2584() {
55    }
56}
57