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.
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.length1 <= n <= 1041 <= nums[i] <= 106In #2584 Split the Array to Make Coprime Products, the goal is to find a split index where the product of the left subarray and the product of the right subarray are coprime (their gcd equals 1). Instead of directly computing large products, the key insight is to analyze prime factors of each number.
First, factorize every element and track the last occurrence of each prime factor across the array using a hash table. If a prime factor appears on both sides of a split, the two products will share that factor and cannot be coprime. While scanning from left to right, maintain the farthest index where any prime factor seen so far appears again.
If the current index equals this boundary, it means all prime factors in the left segment end there, making a valid split possible. Efficient prime factorization and tracking allow this approach to run in approximately O(n log A) time, where A is the maximum element value.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Prime factor tracking with last occurrence mapping | O(n log A) | O(n) |
| Naive product and GCD checking | O(n^2 log A) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Two numbers with GCD equal to 1 have no common prime divisor.
Find the prime factorization of the left and right sides and check if they share a prime divisor.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Two numbers are coprime if they share no common prime factors. By tracking prime factors instead of multiplying numbers directly, we can determine whether the left and right segments share any factor without computing huge products.
Problems involving prime factorization, GCD logic, and partitioning arrays are common in technical interviews. Variants of this problem test knowledge of number theory, hash maps, and greedy boundary tracking, which are frequently assessed in top tech company interviews.
A hash map is typically used to store the last occurrence of each prime factor found in the array. This allows quick updates and checks while scanning the array, ensuring that overlapping prime factors across partitions are detected efficiently.
The optimal approach uses prime factorization and tracks the last occurrence of each prime factor in the array. While scanning from left to right, maintain the farthest boundary where any seen prime reappears. If the current index matches that boundary, the array can be split so the two products are coprime.