# Split the Array to Make Coprime Products
**Difficulty:** HARD
[External](https://leetcode.com/problems/split-the-array-to-make-coprime-products)
Canonical: https://scaleengineer.com/dsa/problems/split-the-array-to-make-coprime-products
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Data structures:** Array, Hash Table
**Companies:** [Zomato](https://scaleengineer.com/companies/zomato)
---
## 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:**

![](https://assets.glich.co/dsa/split-the-array-to-make-coprime-products/image0.PNG) 

**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:**

![](https://assets.glich.co/dsa/split-the-array-to-make-coprime-products/image1.PNG) 

**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`

# Approaches
## Brute-Force with On-the-Fly Factorization
This approach directly translates the problem statement into code. For every possible split point, it calculates the set of unique prime factors for the left and right sub-arrays and then checks if these two sets are disjoint. A split is valid if the sets have no common prime factors.
**Time:** O(n^2 * sqrt(M)) · **Space:** O(P)
**Pros:** Simple to understand and implement.; It is a direct application of the problem's definition.
**Cons:** Extremely inefficient and will lead to a 'Time Limit Exceeded' error on larger test cases.; Repeatedly calculates prime factors for the same numbers in different iterations.
### Explanation
The core of this method is to test each potential split index `i` from `0` to `n-2`. For each `i`, we need to determine if the product of elements `nums[0...i]` is coprime with the product of elements `nums[i+1...n-1]`. Instead of calculating the products, which could be enormous, we work with their prime factors. Two numbers are coprime if and only if they share no common prime factors.

We implement a helper function, `getPrimeFactors`, to find the unique prime factors of any given number. Then, for each split `i`, we build two sets: one for all prime factors of the left part and one for all prime factors of the right part. We then check for an intersection between these two sets. If the intersection is empty, we've found our answer. Since the problem asks for the smallest index, the first one we find will be the solution.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    // Helper to get prime factors by trial division
    private Set<Integer> getPrimeFactors(int n) {
        Set<Integer> factors = new HashSet<>();
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                factors.add(i);
                while (n % i == 0) {
                    n /= i;
                }
            }
        }
        if (n > 1) {
            factors.add(n);
        }
        return factors;
    }

    public int findValidSplit(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return -1;
        }

        for (int i = 0; i < n - 1; i++) {
            Set<Integer> leftFactors = new HashSet<>();
            for (int j = 0; j <= i; j++) {
                leftFactors.addAll(getPrimeFactors(nums[j]));
            }

            Set<Integer> rightFactors = new HashSet<>();
            for (int k = i + 1; k < n; k++) {
                rightFactors.addAll(getPrimeFactors(nums[k]));
            }

            boolean commonFactorFound = false;
            for (int factor : leftFactors) {
                if (rightFactors.contains(factor)) {
                    commonFactorFound = true;
                    break;
                }
            }

            if (!commonFactorFound) {
                return i;
            }
        }

        return -1;
    }
}
```
### Algorithm
- Create a helper function `getPrimeFactors(int n)` that finds all unique prime factors of a number `n` using trial division. It iterates from 2 up to `sqrt(n)`.
- Iterate through each possible split index `i` from `0` to `n - 2`.
- For each `i`, initialize two empty sets, `leftFactors` and `rightFactors`.
- Populate `leftFactors` by iterating from `j = 0` to `i`, getting the prime factors of `nums[j]`, and adding them to the set.
- Populate `rightFactors` by iterating from `k = i + 1` to `n - 1`, getting the prime factors of `nums[k]`, and adding them to the set.
- Check for any common elements between `leftFactors` and `rightFactors`. A simple way is to iterate through one set and check for existence in the other.
- If no common factors are found, the split at `i` is valid. Since we are iterating from the smallest `i`, this is the first valid split, so we return `i`.
- If the loop completes without finding any valid split, it means no such split exists. Return `-1`.

## Single Pass with Pre-computation and Frequency Maps
A much more efficient approach involves pre-computation and a single pass over the array. The key insight is that a split at index `i` is invalid if and only if there is some prime `p` that divides a number in `nums[0...i]` and also divides a number in `nums[i+1...n-1]`. We can track these 'common' primes as we iterate through the possible split points.
**Time:** O(M log(log(M)) + n * log(M)) · **Space:** O(M + P)
**Pros:** Highly efficient and passes the given constraints.; Processes the array in a single pass after an initial setup, avoiding redundant work.
**Cons:** Requires significant auxiliary space `O(M)` for the sieve array.; Implementation is more complex due to the sieve and frequency map management.
### Explanation
This optimized method avoids redundant calculations by first pre-computing necessary information. We use a Sieve to find the smallest prime factor (SPF) for all numbers up to `10^6`. This allows us to find the prime factors of any number `k` efficiently in `O(log k)` time.

First, we iterate through the entire array once to build a frequency map, `totalFreq`, which counts how many numbers in the array are divisible by each prime. For example, if `nums = [6, 10]`, the prime `2` appears in both numbers, so `totalFreq[2]` would be 2.

Next, we iterate from `i = 0` to `n-2`, simulating the split. We maintain a `leftFreq` map for the left side of the split and a `commonFactors` set. As we process `nums[i]`, we move its prime factors from the conceptual 'right' side to the 'left' side by updating `leftFreq`. We use `totalFreq` and `leftFreq` to determine if a prime factor currently exists on both sides. If `0 < leftFreq[p] < totalFreq[p]`, then prime `p` is a common factor. We update the `commonFactors` set accordingly. If at any point this set becomes empty, we have found the smallest valid split.

```java
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class Solution {
    private static final int MAX_VAL = 1000001;
    private int[] spf = new int[MAX_VAL];

    private void sieve() {
        if (spf[1] == 1) return; // Sieve already computed in a previous test case
        spf[1] = 1;
        for (int i = 2; i < MAX_VAL; i++) {
            spf[i] = i;
        }
        for (int i = 2; i * i < MAX_VAL; i++) {
            if (spf[i] == i) { // i is prime
                for (int j = i * i; j < MAX_VAL; j += i) {
                    if (spf[j] == j) { // If spf[j] is not set yet
                        spf[j] = i;
                    }
                }
            }
        }
    }

    private Set<Integer> getPrimeFactors(int n) {
        Set<Integer> factors = new HashSet<>();
        while (n != 1) {
            factors.add(spf[n]);
            n = n / spf[n];
        }
        return factors;
    }

    public int findValidSplit(int[] nums) {
        sieve();
        int n = nums.length;

        Map<Integer, Integer> totalFreq = new HashMap<>();
        for (int num : nums) {
            for (int factor : getPrimeFactors(num)) {
                totalFreq.put(factor, totalFreq.getOrDefault(factor, 0) + 1);
            }
        }

        Map<Integer, Integer> leftFreq = new HashMap<>();
        Set<Integer> commonFactors = new HashSet<>();

        for (int i = 0; i < n - 1; i++) {
            for (int factor : getPrimeFactors(nums[i])) {
                int currentLeftCount = leftFreq.getOrDefault(factor, 0);
                // If factor is appearing on the left for the first time
                if (currentLeftCount == 0) {
                    // And it exists on the right, it becomes a common factor
                    if (totalFreq.get(factor) > 1) {
                        commonFactors.add(factor);
                    }
                }
                
                leftFreq.put(factor, currentLeftCount + 1);

                // If all occurrences of the factor are now on the left, it's no longer common
                if (leftFreq.get(factor).equals(totalFreq.get(factor))) {
                    commonFactors.remove(factor);
                }
            }

            if (commonFactors.isEmpty()) {
                return i;
            }
        }

        return -1;
    }
}
```
### Algorithm
- **Pre-computation:**
  - Use a Sieve of Eratosthenes to pre-compute the Smallest Prime Factor (SPF) for all numbers up to the maximum possible value in `nums` (10^6). This allows for fast factorization.
  - Create a helper function `getPrimeFactors(n)` that uses the SPF array to find the unique prime factors of `n` in `O(log n)` time.
- **Count Total Factor Occurrences:**
  - Create a frequency map, `totalFreq`, to store how many numbers in the `nums` array are divisible by each prime factor. Iterate through `nums`, get the factors for each number, and populate this map.
- **Single Pass Simulation:**
  - Initialize an empty frequency map `leftFreq` (to count factors on the left side of the split) and an empty set `commonFactors` (to track primes that exist on both sides).
  - Iterate with index `i` from `0` to `n-2`:
    - For the current number `nums[i]`, get its prime factors.
    - For each factor `p` of `nums[i]`:
      - Increment its count in `leftFreq`.
      - If this is the first time `p` appears on the left side and it also exists on the right (i.e., `totalFreq[p] > leftFreq[p]`), add `p` to `commonFactors`.
      - If all occurrences of `p` are now on the left side (i.e., `totalFreq[p] == leftFreq[p]`), remove `p` from `commonFactors`.
    - After processing `nums[i]`, if the `commonFactors` set is empty, it means the split at `i` is valid. Return `i`.
- If the loop finishes, no valid split was found, so return `-1`.

# Solutions
### Java

```java
class Solution { public int findValidSplit ( int [] nums ) { Map < Integer , Integer > first = new HashMap <>(); int n = nums . length ; int [] last = new int [ n ]; for ( int i = 0 ; i < n ; ++ i ) { last [ i ] = i ; } for ( int i = 0 ; i < n ; ++ i ) { int x = nums [ i ]; for ( int j = 2 ; j <= x / j ; ++ j ) { if ( x % j == 0 ) { if ( first . containsKey ( j )) { last [ first . get ( j )] = i ; } else { first . put ( j , i ); } while ( x % j == 0 ) { x /= j ; } } } if ( x > 1 ) { if ( first . containsKey ( x )) { last [ first . get ( x )] = i ; } else { first . put ( x , i ); } } } int mx = last [ 0 ]; for ( int i = 0 ; i < n ; ++ i ) { if ( mx < i ) { return mx ; } mx = Math . max ( mx , last [ i ]); } return - 1 ; } }
```

### CPP

```cpp
class Solution {
public:
  int findValidSplit(vector<int> &nums) {
    unordered_map<int, int> first;
    int n = nums.size();
    vector<int> last(n);
    iota(last.begin(), last.end(), 0);
    for (int i = 0; i < n; ++i) {
      int x = nums[i];
      for (int j = 2; j <= x / j; ++j) {
        if (x % j == 0) {
          if (first.count(j)) {
            last[first[j]] = i;
          } else {
            first[j] = i;
          }
          while (x % j == 0) {
            x /= j;
          }
        }
      }
      if (x > 1) {
        if (first.count(x)) {
          last[first[x]] = i;
        } else {
          first[x] = i;
        }
      }
    }
    int mx = last[0];
    for (int i = 0; i < n; ++i) {
      if (mx < i) {
        return mx;
      }
      mx = max(mx, last[i]);
    }
    return -1;
  }
};

```

### Python

```python
class Solution : def findValidSplit ( self , nums : List [ int ]) -> int : first = {} n = len ( nums ) last = list ( range ( n )) for i , x in enumerate ( nums ): j = 2 while j <= x // j : if x % j == 0 : if j in first : last [ first [ j ]] = i else : first [ j ] = i while x % j == 0 : x //= j j += 1 if x > 1 : if x in first : last [ first [ x ]] = i else : first [ x ] = i mx = last [ 0 ] for i , x in enumerate ( last ): if mx < i : return mx mx = max ( mx , x ) return - 1
```