Split the Array to Make Coprime Products solution and explanation
9 more videos on this problem
Split the Array to Make Coprime Products | Weekly Contest 335codingMohan · 17:19 · 2K views
Split the Array to Make Coprime Products || Prime Factors || Number Theory || Leetcode-2584Aryan Mittal · 23:57 · 1K views
Leetcode Weekly contest 335 - Medium - Split the Array to Make Coprime ProductsPrakhar Agrawal · 14:18 · 1K views
【每日一题】LeetCode 2584. Split the Array to Make Coprime ProductsHuifeng Guan · 15:33 · 564 views
LeetCode Weekly Contest 335 | 2584 : Split the Array to Make Coprime Products SolutionFly with Coding | Newton School · 13:19 · 543 views
2584. Split the Array to Make Coprime Products (Leetcode Medium)Programming Live with Larry · 1:04:40 · 327 views
LeetCode weekly contest 335 l Split the Array to Make Coprime Products l Hindi explanationPawan Kumar Giri · 22:03 · 304 views
Leetcode Weekly Contest 335 | Split the Array to Make Coprime Products | Problem AnalysisTech Pe Charcha with Dpwala · 13:06 · 256 views
[Leetcode Weekly 335] Split the Array to Make Coprime ProductsSandeep Kumar · 19:18 · 104 views
[Eng] Weekly Contest 335 | 2584. Split the Array to Make Coprime ProductsCyCode · 8:30 · 37 views
The problem
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 indexi = 0is valid because2and9are coprime, while a split at the indexi = 1is not valid because6and3are not coprime. A split at the indexi = 2is not valid becausei == 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] <= 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.
from math import gcd
def split_array_coprime(nums):
n = len(nums)
prefix_product = [0] * n
suffix_product = [0] * n
prefix_product[0] = nums[0]
suffix_product[n - 1] = nums[n - 1]
for i in range(1, n):
prefix_product[i] = prefix_product[i - 1] * nums[i]
for i in range(n - 2, -1, -1):
suffix_product[i] = suffix_product[i + 1] * nums[i]
for i in range(n - 1):
if gcd(prefix_product[i], suffix_product[i + 1]) == 1:
return i
return -1
nums = [4, 7, 8, 15, 3, 5]
print(split_array_coprime(nums))import java.util.*;
public class SplitArrayCoprime {
public static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
public static int splitArrayCoprime(int[] nums) {
int n = nums.length;
int[] prefixProduct = new int[n];
int[] suffixProduct = new int[n];
prefixProduct[0] = nums[0];
suffixProduct[n - 1] = nums[n - 1];
for (int i = 1; i < n; i++) {
prefixProduct[i] = prefixProduct[i - 1] * nums[i];
}
for (int i = n - 2; i >= 0; i--) {
suffixProduct[i] = suffixProduct[i + 1] * nums[i];
}
for (int i = 0; i < n - 1; i++) {
if (gcd(prefixProduct[i], suffixProduct[i + 1]) == 1) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
int[] nums = {4, 7, 8, 15, 3, 5};
System.out.println(splitArrayCoprime(nums));
}
}#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int splitArrayCoprime(vector<int>& nums) {
int n = nums.size();
vector<int> prefixProduct(n), suffixProduct(n);
prefixProduct[0] = nums[0];
suffixProduct[n - 1] = nums[n - 1];
for (int i = 1; i < n; i++) {
prefixProduct[i] = prefixProduct[i - 1] * nums[i];
}
for (int i = n - 2; i >= 0; i--) {
suffixProduct[i] = suffixProduct[i + 1] * nums[i];
}
for (int i = 0; i < n - 1; i++) {
if (gcd(prefixProduct[i], suffixProduct[i + 1]) == 1) {
return i;
}
}
return -1;
}
int main() {
vector<int> nums = {4, 7, 8, 15, 3, 5};
cout << splitArrayCoprime(nums) << endl;
return 0;
}function gcd(a, b) {
while (b != 0) {
let temp = b;
b = a % b;
a = temp;
}
return a;
}
function splitArrayCoprime(nums) {
const n = nums.length;
const prefixProduct = new Array(n).fill(0);
const suffixProduct = new Array(n).fill(0);
prefixProduct[0] = nums[0];
suffixProduct[n - 1] = nums[n - 1];
for (let i = 1; i < n; i++) {
prefixProduct[i] = prefixProduct[i - 1] * nums[i];
}
for (let i = n - 2; i >= 0; i--) {
suffixProduct[i] = suffixProduct[i + 1] * nums[i];
}
for (let i = 0; i < n - 1; i++) {
if (gcd(prefixProduct[i], suffixProduct[i + 1]) === 1) {
return i;
}
}
return -1;
}
const nums = [4, 7, 8, 15, 3, 5];
console.log(splitArrayCoprime(nums));#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<math.h>
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int splitArrayCoprime(int* nums, int numsSize) {
int prefixProduct[numsSize];
int suffixProduct[numsSize];
prefixProduct[0] = nums[0];
suffixProduct[numsSize - 1] = nums[numsSize - 1];
for(int i = 1; i < numsSize; i++) {
prefixProduct[i] = prefixProduct[i - 1] * nums[i];
}
for(int i = numsSize - 2; i >= 0; i--) {
suffixProduct[i] = suffixProduct[i + 1] * nums[i];
}
for(int i = 0; i < numsSize - 1; i++) {
if(gcd(prefixProduct[i], suffixProduct[i + 1]) == 1) {
return i;
}
}
return -1;
}
int main() {
int nums[] = {4, 7, 8, 15, 3, 5};
int numsSize = sizeof(nums) / sizeof(nums[0]);
int result = splitArrayCoprime(nums, numsSize);
printf("%d\n", result);
return 0;
}using System;
public class SplitArrayCoprime {
public static int Gcd(int a, int b) {
return b == 0 ? a : Gcd(b, a % b);
}
public static int SplitArrayCoprimeMethod(int[] nums) {
int n = nums.Length;
int[] prefixProduct = new int[n];
int[] suffixProduct = new int[n];
prefixProduct[0] = nums[0];
suffixProduct[n - 1] = nums[n - 1];
for (int i = 1; i < n; i++) {
prefixProduct[i] = prefixProduct[i - 1] * nums[i];
}
for (int i = n - 2; i >= 0; i--) {
suffixProduct[i] = suffixProduct[i + 1] * nums[i];
}
for (int i = 0; i < n - 1; i++) {
if (Gcd(prefixProduct[i], suffixProduct[i + 1]) == 1) {
return i;
}
}
return -1;
}
public static void Main(string[] args) {
int[] nums = {4, 7, 8, 15, 3, 5};
Console.WriteLine(SplitArrayCoprimeMethod(nums));
}
}This Python solution utilizes lists to calculate prefix and suffix products, and a loop to check possible splits for coprimeness using the gcd function from the math module.
Time Complexity: O(n), where n is the length of nums. Space Complexity: O(n) due to the storage of prefix and suffix products.
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.
from math import gcd
def split_array_coprime(nums):
prefix = 1
suffix = 1
for num in nums:
suffix *= num
for i in range(len(nums) - 1):
prefix *= nums[i]
suffix //= nums[i]
if gcd(prefix, suffix) == 1:
return i
return -1
nums = [4, 7, 8, 15, 3, 5]
print(split_array_coprime(nums))public class SplitArrayCoprime {
public static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
public static int splitArrayCoprime(int[] nums) {
int n = nums.length;
int prefix = 1;
int suffix = 1;
for (int num : nums) {
suffix *= num;
}
for (int i = 0; i < n - 1; i++) {
prefix *= nums[i];
suffix /= nums[i];
if (gcd(prefix, suffix) == 1) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
int[] nums = {4, 7, 8, 15, 3, 5};
System.out.println(splitArrayCoprime(nums));
}
}#include <iostream>
#include <numeric>
using namespace std;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int splitArrayCoprime(vector<int>& nums) {
int prefix = 1;
int suffix = 1;
for (int num : nums) {
suffix *= num;
}
for (size_t i = 0; i < nums.size() - 1; ++i) {
prefix *= nums[i];
suffix /= nums[i];
if (gcd(prefix, suffix) == 1) {
return i;
}
}
return -1;
}
int main() {
vector<int> nums = {4, 7, 8, 15, 3, 5};
cout << splitArrayCoprime(nums) << endl;
return 0;
}function gcd(a, b) {
while (b != 0) {
let temp = b;
b = a % b;
a = temp;
}
return a;
}
function splitArrayCoprime(nums) {
let prefix = 1;
let suffix = 1;
for (let num of nums) {
suffix *= num;
}
for (let i = 0; i < nums.length - 1; i++) {
prefix *= nums[i];
suffix /= nums[i];
if (gcd(prefix, suffix) === 1) {
return i;
}
}
return -1;
}
const nums = [4, 7, 8, 15, 3, 5];
console.log(splitArrayCoprime(nums));#include<stdio.h>
#include<math.h>
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int splitArrayCoprime(int* nums, int numsSize) {
int prefix = 1;
int suffix = 1;
for (int i = 0; i < numsSize; i++) {
suffix *= nums[i];
}
for (int i = 0; i < numsSize - 1; i++) {
prefix *= nums[i];
suffix /= nums[i];
if (gcd(prefix, suffix) == 1) {
return i;
}
}
return -1;
}
int main() {
int nums[] = {4, 7, 8, 15, 3, 5};
int numsSize = sizeof(nums) / sizeof(nums[0]);
int result = splitArrayCoprime(nums, numsSize);
printf("%d\n", result);
return 0;
}using System;
public class SplitArrayCoprime {
public static int Gcd(int a, int b) {
return b == 0 ? a : Gcd(b, a % b);
}
public static int SplitArrayCoprimeMethod(int[] nums) {
int prefix = 1;
int suffix = 1;
foreach (int num in nums) {
suffix *= num;
}
for (int i = 0; i < nums.Length - 1; i++) {
prefix *= nums[i];
suffix /= nums[i];
if (Gcd(prefix, suffix) == 1) {
return i;
}
}
return -1;
}
public static void Main(string[] args) {
int[] nums = {4, 7, 8, 15, 3, 5};
Console.WriteLine(SplitArrayCoprimeMethod(nums));
}
}This Python solution uses cumulative product updates with in-place gcd checks to efficiently find the valid split index.
Time Complexity: O(n), Space Complexity: O(1).
Approach 3: Default Approach
func findValidSplit(nums []int) int {
first := map[int]int{}
n := len(nums)
last := make([]int, n)
for i := range last {
last[i] = i
}
for i, x := range nums {
for j := 2; j <= x/j; j++ {
if x%j == 0 {
if k, ok := first[j]; ok {
last[k] = i
} else {
first[j] = i
}
for x%j == 0 {
x /= j
}
}
}
if x > 1 {
if k, ok := first[x]; ok {
last[k] = i
} else {
first[x] = i
}
}
}
mx := last[0]
for i, x := range last {
if mx < i {
return mx
}
mx = max(mx, x)
}
return -1
}Complexity comparison
| Approach | Complexity |
|---|---|
| Prefix and Suffix Product Approach | Time Complexity: O(n), where n is the length of nums. Space Complexity: O(n) due to the storage of prefix and suffix products. |
| Cumulative Product with Single Pass | Time Complexity: O(n), Space Complexity: O(1). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix and Suffix Product Approach | O(n log A) | O(n) | When you want explicit prefix and suffix factor tracking for clarity |
| Cumulative Product with Single Pass | O(n log A) | O(n) | General optimal solution using last occurrence of prime factors |
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.