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 indexi 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.

Examples

Example 1

index prefixProduct suffixProduct gcd
0 4 12600 4
1 28 1800 4
2 224 225 1
3 3360 15 15
4 10080 5 5 
1
2
3
4

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

index prefixProduct suffixProduct gcd
0 4 12600 4
1 28 1800 4
2 420 120 60
3 3360 15 15
4 10080 5 5 
1
2
3
4

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 <= 10^4
  • 1 <= nums[i] <= 10^6

Solution

Method 1 – Prime Factor Coverage (Number Theory)

Intuition

If a prime factor appears in both the prefix and suffix products, the two products cannot be coprime. Track the last occurrence of each prime factor in the array, and find the earliest split where all prime factors in the prefix are not present in the suffix.

Approach

  1. For each number, factorize it and record the last index where each prime factor appears.
  2. Iterate through the array, maintaining the maximum last index of all prime factors seen so far.
  3. The earliest split index is where the current index equals the maximum last index of all prime factors in the prefix.
  4. If no such split exists, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    int findValidSplit(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> last;
        auto factorize = [](int x) {
            vector<int> f;
            for (int d = 2; d * d <= x; ++d) {
                if (x % d == 0) {
                    f.push_back(d);
                    while (x % d == 0) x /= d;
                }
            }
            if (x > 1) f.push_back(x);
            return f;
        };
        for (int i = 0; i < n; ++i) {
            for (int p : factorize(nums[i])) last[p] = i;
        }
        int maxLast = 0;
        for (int i = 0; i < n-1; ++i) {
            for (int p : factorize(nums[i])) maxLast = max(maxLast, last[p]);
            if (maxLast == i) return i;
        }
        return -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

func findValidSplit(nums []int) int {
    n := len(nums)
    last := map[int]int{}
    factorize := func(x int) []int {
        f := []int{}
        for d := 2; d*d <= x; d++ {
            if x%d == 0 {
                f = append(f, d)
                for x%d == 0 { x /= d }
            }
        }
        if x > 1 { f = append(f, x) }
        return f
    }
    for i, v := range nums {
        for _, p := range factorize(v) {
            last[p] = i
        }
    }
    maxLast := 0
    for i := 0; i < n-1; i++ {
        for _, p := range factorize(nums[i]) {
            if last[p] > maxLast { maxLast = last[p] }
        }
        if maxLast == i { return i }
    }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    public int findValidSplit(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer> last = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            for (int p : factorize(nums[i])) last.put(p, i);
        }
        int maxLast = 0;
        for (int i = 0; i < n-1; ++i) {
            for (int p : factorize(nums[i])) maxLast = Math.max(maxLast, last.get(p));
            if (maxLast == i) return i;
        }
        return -1;
    }
    private List<Integer> factorize(int x) {
        List<Integer> f = new ArrayList<>();
        for (int d = 2; d * d <= x; ++d) {
            if (x % d == 0) {
                f.add(d);
                while (x % d == 0) x /= d;
            }
        }
        if (x > 1) f.add(x);
        return f;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
    fun findValidSplit(nums: IntArray): Int {
        val n = nums.size
        val last = mutableMapOf<Int, Int>()
        fun factorize(x: Int): List<Int> {
            val f = mutableListOf<Int>()
            var y = x
            var d = 2
            while (d * d <= y) {
                if (y % d == 0) {
                    f.add(d)
                    while (y % d == 0) y /= d
                }
                d++
            }
            if (y > 1) f.add(y)
            return f
        }
        for (i in 0 until n) {
            for (p in factorize(nums[i])) last[p] = i
        }
        var maxLast = 0
        for (i in 0 until n-1) {
            for (p in factorize(nums[i])) maxLast = maxOf(maxLast, last[p]!!)
            if (maxLast == i) return i
        }
        return -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

def findValidSplit(nums: list[int]) -> int:
    def factorize(x: int) -> list[int]:
        f = []
        d = 2
        while d * d <= x:
            if x % d == 0:
                f.append(d)
                while x % d == 0:
                    x //= d
            d += 1
        if x > 1:
            f.append(x)
        return f
    n = len(nums)
    last = {}
    for i, v in enumerate(nums):
        for p in factorize(v):
            last[p] = i
    max_last = 0
    for i in range(n-1):
        for p in factorize(nums[i]):
            max_last = max(max_last, last[p])
        if max_last == i:
            return i
    return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

impl Solution {
    pub fn find_valid_split(nums: Vec<i32>) -> i32 {
        fn factorize(x: i32) -> Vec<i32> {
            let mut f = vec![];
            let mut y = x;
            let mut d = 2;
            while d * d <= y {
                if y % d == 0 {
                    f.push(d);
                    while y % d == 0 { y /= d; }
                }
                d += 1;
            }
            if y > 1 { f.push(y); }
            f
        }
        let n = nums.len();
        let mut last = std::collections::HashMap::new();
        for (i, &v) in nums.iter().enumerate() {
            for p in factorize(v) {
                last.insert(p, i);
            }
        }
        let mut max_last = 0;
        for i in 0..n-1 {
            for p in factorize(nums[i]) {
                if let Some(&idx) = last.get(&p) {
                    if idx > max_last { max_last = idx; }
                }
            }
            if max_last == i { return i as i32; }
        }
        -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    findValidSplit(nums: number[]): number {
        function factorize(x: number): number[] {
            const f: number[] = [];
            let d = 2;
            while (d * d <= x) {
                if (x % d === 0) {
                    f.push(d);
                    while (x % d === 0) x /= d;
                }
                d++;
            }
            if (x > 1) f.push(x);
            return f;
        }
        const n = nums.length;
        const last: Record<number, number> = {};
        for (let i = 0; i < n; ++i) {
            for (const p of factorize(nums[i])) last[p] = i;
        }
        let maxLast = 0;
        for (let i = 0; i < n-1; ++i) {
            for (const p of factorize(nums[i])) maxLast = Math.max(maxLast, last[p]);
            if (maxLast === i) return i;
        }
        return -1;
    }
}

Complexity

  • ⏰ Time complexity: O(n * sqrt(max(nums))) – Each number is factorized, and we scan the array.
  • 🧺 Space complexity: O(n) – Hash map for last occurrence of each prime factor.