Problem

You are given an integer array nums.

Splitting of an integer array nums into subarrays is valid if:

  • the greatest common divisor of the first and last elements of each subarray is greater than 1, and
  • each element of nums belongs to exactly one subarray.

Return theminimum number of subarrays in a valid subarray splitting of nums. If a valid subarray splitting is not possible, return -1.

Note that:

  • The greatest common divisor of two numbers is the largest positive integer that evenly divides both numbers.
  • A subarray is a contiguous non-empty part of an array.

Examples

Example 1:

1
2
3
4
5
6

Input: nums = [2,6,3,4,3]
Output: 2
Explanation: We can create a valid split in the following way: [2,6] | [3,4,3].
- The starting element of the 1st subarray is 2 and the ending is 6. Their greatest common divisor is 2, which is greater than 1.
- The starting element of the 2nd subarray is 3 and the ending is 3. Their greatest common divisor is 3, which is greater than 1.
It can be proved that 2 is the minimum number of subarrays that we can obtain in a valid split.

Example 2:

1
2
3
4
5
6

Input: nums = [3,5]
Output: 2
Explanation: We can create a valid split in the following way: [3] | [5].
- The starting element of the 1st subarray is 3 and the ending is 3. Their greatest common divisor is 3, which is greater than 1.
- The starting element of the 2nd subarray is 5 and the ending is 5. Their greatest common divisor is 5, which is greater than 1.
It can be proved that 2 is the minimum number of subarrays that we can obtain in a valid split.

Example 3:

1
2
3

Input: nums = [1,2,1]
Output: -1
Explanation: It is impossible to create valid split.

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 10^5

Solution

Method 1 – Dynamic Programming (Greedy Split)

Intuition

We want to split the array into the minimum number of contiguous subarrays such that the GCD of the first and last element of each subarray is greater than 1. We can use DP: for each position, try to extend the current subarray as far as possible, and split only when necessary.

Approach

Let dp[i] be the minimum number of subarrays for nums[0..i]. For each j < i, if gcd(nums[j], nums[i]) > 1, we can split at j. We initialize dp[0] = 1, and for each i, check all possible splits.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include <numeric>
class Solution {
public:
    int minimumSubarrays(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1e9);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= i; ++j) {
                if (gcd(nums[j], nums[i]) > 1) {
                    dp[i] = min(dp[i], (j ? dp[j-1] : 0) + 1);
                }
            }
        }
        return dp[n-1] >= 1e9 ? -1 : dp[n-1];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}
func minimumSubarrays(nums []int) int {
    n := len(nums)
    dp := make([]int, n)
    for i := range dp { dp[i] = 1e9 }
    for i := 0; i < n; i++ {
        for j := 0; j <= i; j++ {
            if gcd(nums[j], nums[i]) > 1 {
                prev := 0
                if j > 0 { prev = dp[j-1] }
                if prev+1 < dp[i] { dp[i] = prev+1 }
            }
        }
    }
    if dp[n-1] >= 1e9 { return -1 }
    return dp[n-1]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    private int gcd(int a, int b) {
        while (b != 0) {
            int t = b; b = a % b; a = t;
        }
        return a;
    }
    public int minimumSubarrays(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (gcd(nums[j], nums[i]) > 1) {
                    int prev = j > 0 ? dp[j-1] : 0;
                    dp[i] = Math.min(dp[i], prev+1);
                }
            }
        }
        return dp[n-1] == Integer.MAX_VALUE ? -1 : dp[n-1];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    private fun gcd(a: Int, b: Int): Int {
        var x = a; var y = b
        while (y != 0) { val t = y; y = x % y; x = t }
        return x
    }
    fun minimumSubarrays(nums: IntArray): Int {
        val n = nums.size
        val dp = IntArray(n) { Int.MAX_VALUE }
        for (i in 0 until n) {
            for (j in 0..i) {
                if (gcd(nums[j], nums[i]) > 1) {
                    val prev = if (j > 0) dp[j-1] else 0
                    dp[i] = minOf(dp[i], prev+1)
                }
            }
        }
        return if (dp[n-1] == Int.MAX_VALUE) -1 else dp[n-1]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

from math import gcd
class Solution:
    def minimumSubarrays(self, nums: list[int]) -> int:
        n = len(nums)
        dp = [float('inf')] * n
        for i in range(n):
            for j in range(i+1):
                if gcd(nums[j], nums[i]) > 1:
                    prev = dp[j-1] if j > 0 else 0
                    dp[i] = min(dp[i], prev+1)
        return -1 if dp[-1] == float('inf') else dp[-1]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn minimum_subarrays(nums: Vec<i32>) -> i32 {
        fn gcd(mut a: i32, mut b: i32) -> i32 {
            while b != 0 { let t = b; b = a % b; a = t; } a
        }
        let n = nums.len();
        let mut dp = vec![i32::MAX; n];
        for i in 0..n {
            for j in 0..=i {
                if gcd(nums[j], nums[i]) > 1 {
                    let prev = if j > 0 { dp[j-1] } else { 0 };
                    dp[i] = dp[i].min(prev+1);
                }
            }
        }
        if dp[n-1] == i32::MAX { -1 } else { dp[n-1] }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

function gcd(a: number, b: number): number {
    while (b !== 0) { let t = b; b = a % b; a = t; } return a;
}
class Solution {
    minimumSubarrays(nums: number[]): number {
        const n = nums.length;
        const dp = Array(n).fill(Infinity);
        for (let i = 0; i < n; i++) {
            for (let j = 0; j <= i; j++) {
                if (gcd(nums[j], nums[i]) > 1) {
                    const prev = j > 0 ? dp[j-1] : 0;
                    dp[i] = Math.min(dp[i], prev+1);
                }
            }
        }
        return dp[n-1] === Infinity ? -1 : dp[n-1];
    }
}

Complexity

  • ⏰ Time complexity: O(n^2) — For each end, try all starts.
  • 🧺 Space complexity: O(n) — For DP array.