2584. Split the Array to Make Coprime Products

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.

• 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.

Return the smallest index i at which the array can be split validly or -1 if there is no such split.

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.

class Solution {
    unordered_map<int, int> helper(vector<int> A) {
        unordered_map<int, int> res;
        for(int i = 0; i < A.size(); i++) {
            for(int j = 2; j * j <= A[i]; j++) {
                if(A[i] % j) continue;
                res[j] = i;
                while(A[i] % j == 0) A[i] /= j;
            }
            if(A[i] != 1) res[A[i]] = i;
        }
        return res;
    }
public:
    int findValidSplit(vector<int>& nums) {
        unordered_map<int, int> mp = helper(nums);
        int ma = 0;
        for(int i = 0; i < nums.size() and i <= ma; i++) {
            for(int j = 2; j * j <= nums[i]; j++) {
                if(nums[i] % j) continue;
                ma = max(ma,mp[j]);
                while(nums[i] % j == 0) nums[i] /= j;
            }
            if(nums[i] != 1) ma = max(ma,mp[nums[i]]);
        }
        if(ma == nums.size() - 1) return -1;
        return ma;
    }
};