# 2584. Split the Array to Make Coprime Products¶

• Time: $O(n\sqrt{n})$
• Space: $O(n\sqrt{n})$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 class Solution { public: int findValidSplit(vector& nums) { unordered_map leftPrimeFactors; unordered_map rightPrimeFactors; for (const int num : nums) for (const int primeFactor : getPrimeFactors(num)) ++rightPrimeFactors[primeFactor]; for (int i = 0; i < nums.size() - 1; ++i) { for (const int primeFactor : getPrimeFactors(nums[i])) { if (--rightPrimeFactors[primeFactor] == 0) { // rightPrimeFactors[primeFactor] == 0, so no need to track // leftPrimeFactors[primeFactor]. rightPrimeFactors.erase(primeFactor); leftPrimeFactors.erase(primeFactor); } else { // Otherwise, need to track leftPrimeFactors[primeFactor]. ++leftPrimeFactors[primeFactor]; } } if (leftPrimeFactors.empty()) return i; } return -1; } private: // Gets the prime factors under sqrt(10^6). vector getPrimeFactors(int num) { vector primeFactors; for (int divisor = 2; divisor <= min(1000, num); ++divisor) if (num % divisor == 0) { primeFactors.push_back(divisor); while (num % divisor == 0) num /= divisor; } // Handle the case that num contains a prime factor > 1000. if (num > 1) primeFactors.push_back(num); return primeFactors; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 class Solution { public int findValidSplit(int[] nums) { Map leftPrimeFactors = new HashMap<>(); Map rightPrimeFactors = new HashMap<>(); for (final int num : nums) for (final int primeFactor : getPrimeFactors(num)) rightPrimeFactors.merge(primeFactor, 1, Integer::sum); for (int i = 0; i < nums.length - 1; ++i) { for (final int primeFactor : getPrimeFactors(nums[i])) { rightPrimeFactors.merge(primeFactor, -1, Integer::sum); if (rightPrimeFactors.get(primeFactor) == 0) { // rightPrimeFactors[primeFactor] == 0, so no need to track // leftPrimeFactors[primeFactor]. rightPrimeFactors.remove(primeFactor); leftPrimeFactors.remove(primeFactor); } else { // Otherwise, need to track leftPrimeFactors[primeFactor]. leftPrimeFactors.merge(primeFactor, 1, Integer::sum); } } if (leftPrimeFactors.isEmpty()) return i; } return -1; } // Gets the prime factors under sqrt(10^6). private List getPrimeFactors(int num) { List primeFactors = new ArrayList<>(); for (int divisor = 2; divisor <= Math.min(1000, num); ++divisor) if (num % divisor == 0) { primeFactors.add(divisor); while (num % divisor == 0) num /= divisor; } // Handle the case that num contains a prime factor > 1000. if (num > 1) primeFactors.add(num); return primeFactors; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution: def findValidSplit(self, nums: list[int]) -> int: leftPrimeFactors = collections.Counter() rightPrimeFactors = collections.Counter() def getPrimeFactors(num: int) -> list[int]: """Gets the prime factors under sqrt(10^6).""" primeFactors = [] for divisor in range(2, min(1000, num) + 1): if num % divisor == 0: primeFactors.append(divisor) while num % divisor == 0: num //= divisor # Handle the case that num contains a prime factor > 1000. if num > 1: primeFactors.append(num) return primeFactors for num in nums: for primeFactor in getPrimeFactors(num): rightPrimeFactors[primeFactor] += 1 for i in range(len(nums) - 1): for primeFactor in getPrimeFactors(nums[i]): rightPrimeFactors[primeFactor] -= 1 if rightPrimeFactors[primeFactor] == 0: # rightPrimeFactors[primeFactor] == 0, so no need to track # leftPrimeFactors[primeFactor]. del rightPrimeFactors[primeFactor] del leftPrimeFactors[primeFactor] else: # Otherwise, need to track leftPrimeFactors[primeFactor]. leftPrimeFactors[primeFactor] += 1 if not leftPrimeFactors: return i return -1