2584. Split the Array to Make Coprime Products

Problem

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.

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.

Constraints:

• n == nums.length
• 1 <= n <= 104
• 1 <= nums[i] <= 106

Solution (Java)

class Solution {
    public int findValidSplit(int[] nums) {
        // prime factor freq
        // check left and right
        int n = nums.length;
        Map<Integer, Integer> totalPrimeMap = new HashMap<>();
        Map<Integer, Integer>[] primeMaps = new HashMap[nums.length];
        for (int i = 0; i < n; i++) {
            primeMaps[i] = new HashMap<>();
        }
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            compute(num, primeMaps[i], totalPrimeMap);
        }



        Map<Integer, Integer> primeMapPtr = new HashMap<>();
        for (int i = 0; i < n - 1; i++) {
            // System.out.println("i : " + i);
            if (ok(primeMapPtr, primeMaps[i], totalPrimeMap)) return i;
        }
        return -1;
    }

    private void compute(int x,  Map<Integer, Integer> primeMap, Map<Integer, Integer> totalPrimeMap) {
        for (int i = 2; i <= x / i; i++) {
            if (x % i == 0) {
                int freq = 0;
                while (x % i == 0) {
                    freq++;
                    x /= i;
                }
                primeMap.put(i, primeMap.getOrDefault(i, 0) + freq);
                totalPrimeMap.put(i, totalPrimeMap.getOrDefault(i, 0) + freq);
            }
        }

        if (x > 1) {
            primeMap.put(x, primeMap.getOrDefault(x, 0) + 1);
            totalPrimeMap.put(x, totalPrimeMap.getOrDefault(x, 0) + 1);
        }
    }

    private boolean ok(Map<Integer, Integer> primeMapPtr, Map<Integer, Integer> currPrimeMap, Map<Integer, Integer> totalPrimeMap) {
        for (int p : currPrimeMap.keySet()) {
            primeMapPtr.put(p, primeMapPtr.getOrDefault(p, 0) + currPrimeMap.get(p));
        }

        // check
        for (int p : primeMapPtr.keySet()) {
            if (primeMapPtr.get(p) < totalPrimeMap.get(p)) return false;
        }
        return true;


    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).