LeetCode Solutions Blog

Split the Array to Make Coprime Products

Number: 2647

Difficulty: Hard

Paid? No

Companies: Zomato

Problem Description

You are given a 0-indexed integer array nums of length n. A split at an index i (0 <= i <= n - 2) is considered valid if the product of the first i + 1 elements and the product of the remaining elements are coprime, i.e. their greatest common divisor (gcd) is 1. Return the smallest index i at which the array can be split validly, or -1 if there is no valid split.

Key Insights

Calculating the actual products is infeasible due to potential overflow; instead, focus on prime factors.
Decompose each element into its prime factors using a sieve or trial division.
Represent the product of a subarray by aggregating the counts of prime factors.
Maintain two dictionaries (or hash maps): one for the prefix (first part) and one for the suffix (remaining part).
A valid split will have no common prime factors between the prefix and the suffix (i.e. their intersection is empty).

Space and Time Complexity

Time Complexity: O(n * (log(max(nums)) + p)) where p is the number of distinct prime factors per number.
Space Complexity: O(n + P) where P is the number of distinct primes encountered across the array.

Solution

We avoid computing huge products by working with prime factorizations. First, precompute the overall frequency of each prime factor from all numbers. Then, iterate from the start of the array updating a prefix map with the prime factors of the current number and decreasing these counts from the overall (suffix) map. After processing each number, check if the prefix and suffix share any common prime factor. If they do not share any factor, then the gcd of the two products is 1 and the current index represents a valid split. If no valid split is found after checking all possible indices, return -1.

Code Solutions

# Python solution for "Split the Array to Make Coprime Products"
import math
from collections import defaultdict

# Helper function to perform prime factorization using trial division
def prime_factors(number):
    factors = defaultdict(int)
    # Count the number of 2s that divide number
    while number % 2 == 0:
        factors[2] += 1
        number //= 2
    # n must be odd at this point so skip even numbers
    f = 3
    while f * f <= number:
        while number % f == 0:
            factors[f] += 1
            number //= f
        f += 2
    if number > 1:
        factors[number] += 1
    return factors

def splitTheArray(nums):
    n = len(nums)
    # Store prime factors for each element so we don't factorize repeatedly
    pf_list = [prime_factors(num) for num in nums]
    
    # Build overall map of prime factors for the entire array (suffix map initially)
    overall = defaultdict(int)
    for pf in pf_list:
        for prime, count in pf.items():
            overall[prime] += count
    
    prefix = defaultdict(int)
    
    # Iterate from index 0 to n - 2 to check possible splits
    for i in range(n - 1):
        # Update prefix and decrease in overall (suffix) for current element
        for prime, count in pf_list[i].items():
            prefix[prime] += count
            overall[prime] -= count
            if overall[prime] == 0:
                del overall[prime]  # remove prime from overall if count reaches zero
        
        # Check if prefix and overall share any common prime factor
        valid = True
        for prime in prefix:
            if prime in overall:
                valid = False
                break
        
        if valid:
            return i
    return -1

# Example usage:
# nums = [4,7,8,15,3,5]
# print(splitTheArray(nums))