Split the Array to Make Coprime Products - Practice Coding Problems

Split the Array to Make Coprime Products - 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 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.

Input & Output

Example 1 — Basic Valid Split

$ Input: nums = [2, 3, 3]

› Output: 0

💡 Note: Split at index 0: left product = 2, right product = 3×3 = 9. Since GCD(2,9) = 1, they are coprime.

Example 2 — No Valid Split

$ Input: nums = [2, 6, 3, 4]

› Output: -1

💡 Note: No split position creates coprime products. All splits share common factors between left and right products.

Example 3 — Later Valid Split

$ Input: nums = [4, 7, 8, 15, 3, 5]

› Output: 3

💡 Note: Split at index 3: left product has factors {2,7}, right product has factors {3,5}. No common prime factors.

Constraints

2 ≤ nums.length ≤ 10⁴
1 ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Array

[2, 3, 3] - need to find valid split position

Try Split at i=0

Left: [2] (product=2), Right: [3,3] (product=9)

Check Coprimality

GCD(2, 9) = 1, so they are coprime → valid split

Key Takeaway

🎯 Key Insight: Two numbers are coprime if they share no common prime factors - track factors instead of computing large products

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is that two numbers are coprime if they share no common prime factors. Instead of calculating potentially large products, we can track prime factors and check for intersections. The optimal approach uses prime factorization with hash sets to avoid integer overflow. Time: O(n² × √M), Space: O(n × P).

Common Approaches

Approach	Time	Space	Notes
✓ Prime Factorization with Sets	O(n² × √M)	O(P)	Track prime factors instead of calculating large products to avoid overflow
Two-Pass Prime Factor Optimization	O(n² × √M)	O(n × P)	Pre-calculate all prime factors once, then efficiently check splits using prefix tracking
Brute Force Product Calculation	O(n²)	O(1)	Calculate products directly and compute GCD for each possible split

Prime Factorization with Sets — Algorithm Steps

Get prime factors for each number in the array
For each split, collect prime factors of left and right sides
Check if left and right factor sets have empty intersection

Visualization

Tap to expand

Step-by-Step Walkthrough

Get Prime Factors

2→{2}, 3→{3}, 3→{3}

Check Split i=0

Left factors: {2}, Right factors: {3} → No intersection ✓

Result

First valid split found at index 0

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

void getPrimeFactors(int n, int* factors, int* factorCount) {
    *factorCount = 0;
    if (n < 0) n = -n;
    if (n <= 1) return;
    
    int d = 2;
    while (d * d <= n) {
        if (n % d == 0) {
            factors[(*factorCount)++] = d;
            while (n % d == 0) {
                n /= d;
            }
        }
        d++;
    }
    if (n > 1) {
        factors[(*factorCount)++] = n;
    }
}

bool hasCommonFactor(int* left, int leftCount, int* right, int rightCount) {
    for (int i = 0; i < leftCount; i++) {
        for (int j = 0; j < rightCount; j++) {
            if (left[i] == right[j]) {
                return true;
            }
        }
    }
    return false;
}

int solution(int* nums, int n) {
    for (int i = 0; i < n - 1; i++) {
        int leftFactors[1000] = {0};
        int leftCount = 0;
        
        for (int j = 0; j <= i; j++) {
            int factors[100];
            int factorCount;
            getPrimeFactors(nums[j], factors, &factorCount);
            
            for (int k = 0; k < factorCount; k++) {
                bool exists = false;
                for (int l = 0; l < leftCount; l++) {
                    if (leftFactors[l] == factors[k]) {
                        exists = true;
                        break;
                    }
                }
                if (!exists) {
                    leftFactors[leftCount++] = factors[k];
                }
            }
        }
        
        int rightFactors[1000] = {0};
        int rightCount = 0;
        
        for (int j = i + 1; j < n; j++) {
            int factors[100];
            int factorCount;
            getPrimeFactors(nums[j], factors, &factorCount);
            
            for (int k = 0; k < factorCount; k++) {
                bool exists = false;
                for (int l = 0; l < rightCount; l++) {
                    if (rightFactors[l] == factors[k]) {
                        exists = true;
                        break;
                    }
                }
                if (!exists) {
                    rightFactors[rightCount++] = factors[k];
                }
            }
        }
        
        if (!hasCommonFactor(leftFactors, leftCount, rightFactors, rightCount)) {
            return i;
        }
    }
    
    return -1;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int n = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × √M)

n splits × n elements per split × √M for prime factorization where M is max element value

⚠ Quadratic Growth

Space Complexity

O(P)

P is the number of unique prime factors across all elements

✓ Linear Space

12.5K Views

Medium Frequency

~35 min Avg. Time

342 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prime Factorization with Sets — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler