2584. Split the Array to Make Coprime Products

Description

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

 

Solutions

Solution: Hash Table + Math

• Time complexity: O(nlogMax(nums))
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
const findValidSplit = function (nums) {
  const n = nums.length;
  const leftPrimeFactors = new Set();
  const rightPrimeMap = new Map();

  const getPrimeFactors = num => {
    const factorMap = new Map();

    for (let x = 2; x ** 2 <= num; x++) {
      while (num % x === 0) {
        const count = factorMap.get(x) ?? 0;

        factorMap.set(x, count + 1);
        num /= x;
      }
    }

    if (num > 1) {
      const count = factorMap.get(num) ?? 0;

      factorMap.set(num, count + 1);
    }

    return factorMap;
  };

  for (const num of nums) {
    const factorMap = getPrimeFactors(num);

    for (const [prime, count] of factorMap) {
      const primeCount = rightPrimeMap.get(prime) ?? 0;

      rightPrimeMap.set(prime, primeCount + count);
    }
  }

  for (let index = 0; index < n - 1; index++) {
    const num = nums[index];
    const factorMap = getPrimeFactors(num);

    for (const [prime, count] of factorMap) {
      const primeCount = rightPrimeMap.get(prime) ?? 0;

      if (count >= primeCount) {
        rightPrimeMap.delete(prime);
        leftPrimeFactors.delete(prime);
      } else {
        rightPrimeMap.set(prime, primeCount - count);
        leftPrimeFactors.add(prime);
      }
    }

    if (!leftPrimeFactors.size) return index;
  }

  return -1;
};