Skip to main content
Talentd

Split the Array to Make Coprime Products - Solution & Explanation

HardArrayHash TableMathNumber Theory15 min readAsked at: Zomato
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given an integer array and must split it into two non-empty parts such that the product of the left subarray and the product of the right subarray are coprime. The task is to return the earliest split index where gcd(prefixProduct, suffixProduct) = 1.

The key observation is that two products are coprime if they share no common prime factors. Instead of multiplying large numbers (which quickly overflows), track the prime factors contributing to each side of the split.

Approach 1: Prefix and Suffix Product Approach (O(n log A) time, O(n) space)

This method explicitly models the idea of prefix and suffix products using prime factor tracking. First factorize each number and record which primes appear. Build prefix information by accumulating factors seen so far, and suffix information by tracking factors that appear later in the array. When scanning possible split points, check whether any prime factor exists on both sides. If the prefix and suffix share no common factors, the split is valid. Factorization costs O(log A) per element, giving overall O(n log A) time and O(n) extra space. This approach is straightforward and useful when you want a clear separation between prefix and suffix computations.

Approach 2: Cumulative Product with Single Pass (O(n log A) time, O(n) space)

A more optimized implementation tracks the last occurrence of every prime factor. Factorize each number and store the furthest index where each prime appears. Then scan the array once while maintaining the farthest boundary of any prime factor seen so far. If the current index equals that boundary, all prime factors from the left side end here, meaning none continue into the right side. That index forms a valid split because the two products cannot share factors. This technique uses a hash map for prime tracking and avoids maintaining full prefix/suffix structures.

This problem heavily relies on concepts from number theory, efficient prime factorization on arrays, and fast lookups using a hash table. Managing ranges and boundaries across an array is the core implementation detail.

Recommended for interviews: The single-pass cumulative approach. Interviewers expect you to recognize that multiplying values is unnecessary and that prime factor overlap determines coprimality. Showing the prefix/suffix reasoning demonstrates understanding, but the boundary-tracking solution shows stronger algorithmic insight and cleaner implementation.

Approach 1: Prefix and Suffix Product Approach

This approach involves calculating the prefix product up to each index, as well as the suffix product from each index to the end of the array. By iterating over possible splits, calculate the gcd of the prefix and suffix products to determine if they are coprime.

The function first calculates prefix and suffix products for the given array. It iterates through to find a valid split where the gcd of the prefix and suffix products is 1 (meaning they are coprime). The gcd function uses the Euclidean algorithm.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the array. Space Complexity: O(n) due to the storage for prefix and suffix products.

Try this approach in the editor →

Approach 2: Cumulative Product with Single Pass

This approach seeks to optimize space usage by maintaining cumulative products during a single traversal of the array. Instead of using full prefix and suffix arrays, it updates running products directly and checks coprimeness on-the-fly.

The optimized C solution combines the prefix and suffix product calculation into a single pass, multiplying and dividing by elements of the array as appropriate, to check gcd for coprimeness directly.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), Space Complexity: O(1) since no additional arrays are used.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Prefix and Suffix Product Approach

Time Complexity: O(n), where n is the length of the array. Space Complexity: O(n) due to the storage for prefix and suffix products.

Cumulative Product with Single Pass

Time Complexity: O(n), Space Complexity: O(1) since no additional arrays are used.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Prefix and Suffix Product ApproachO(n log A)O(n)When you want explicit prefix and suffix factor tracking for clarity
Cumulative Product with Single PassO(n log A)O(n)General optimal solution using last occurrence of prime factors

Video Solution

Split the Array to Make Coprime Products | Weekly Contest 335 • codingMohan • 2,602 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Split the Array to Make Coprime Products easy or hard?
Split the Array to Make Coprime Products is classified as a Hard problem. The difficulty comes from recognizing that product gcd checks can be replaced with prime factor overlap tracking, which requires number theory knowledge and careful boundary management.
Split the Array to Make Coprime Products Python/Java solution
Most implementations first factorize each number, store the last index for every prime factor in a hash map, then scan the array while updating the maximum boundary. The earliest index where the scan index equals that boundary is returned. The same logic works in Python, Java, C++, and other languages.
How to solve Split the Array to Make Coprime Products in O(n)?
The array scan itself is O(n), but prime factorization introduces a log(A) factor. The algorithm precomputes the last index where each prime appears, then performs a single pass maintaining the farthest boundary of seen primes. When the scan index equals that boundary, a valid coprime split is found.
What is the best approach for Split the Array to Make Coprime Products?
The most efficient approach tracks the last occurrence of each prime factor and scans the array once while maintaining the farthest boundary of active factors. When the current index reaches that boundary, all factors from the left side end there, meaning the prefix and suffix products are coprime. This runs in O(n log A) time due to prime factorization and uses O(n) extra space.
Is Split the Array to Make Coprime Products asked at Google/Amazon/Meta?
Problems involving prime factorization, gcd properties, and interval boundaries are common in interviews at large tech companies like Google, Amazon, and Meta. Variations of this problem test number theory knowledge combined with hash map tracking and greedy scanning techniques.
What data structure is used in Split the Array to Make Coprime Products?
A hash map is typically used to store the last occurrence of each prime factor across the array. During the scan, variables track the current boundary of active factors. The solution also relies on arrays and prime factorization from number theory.
What is the time complexity of Split the Array to Make Coprime Products?
The typical optimal solution runs in O(n log A) time, where n is the array length and A is the maximum value in the array. Each element is factorized into primes, which costs roughly O(log A). The final scan of the array is linear.

Ready to solve this problem?

Practice Split the Array to Make Coprime Products with our built-in code editor and test cases.

Practice on FleetCode
Previous

Replace Non-Coprime Numbers in Array