Scale Engineer

Split the Array to Make Coprime Products

Hard
#2364Time: O(n^2 * sqrt(M))Space: O(P)1 company
Patterns
MathNumber Theory
Data structures
ArrayHash Table
Companies
Zomato

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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;    }}

Complexity

Time

O(n^2 * sqrt(M))

Space

O(P)

Trade-offs

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.

Solutions

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 ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem