##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2464.html

# 2464. Minimum Subarrays in a Valid Split

## Description

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 the minimum 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.

Example 1:

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:

Input: nums = [3,5]
Output: 2
Explanation: We can create a valid split in the following way:  | .
- 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:

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


Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 105

## Solutions

• class Solution {
private int n;
private int[] f;
private int[] nums;
private int inf = 0x3f3f3f3f;

public int validSubarraySplit(int[] nums) {
n = nums.length;
f = new int[n];
this.nums = nums;
int ans = dfs(0);
return ans < inf ? ans : -1;
}

private int dfs(int i) {
if (i >= n) {
return 0;
}
if (f[i] > 0) {
return f[i];
}
int ans = inf;
for (int j = i; j < n; ++j) {
if (gcd(nums[i], nums[j]) > 1) {
ans = Math.min(ans, 1 + dfs(j + 1));
}
}
f[i] = ans;
return ans;
}

private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}

• class Solution {
public:
const int inf = 0x3f3f3f3f;
int validSubarraySplit(vector<int>& nums) {
int n = nums.size();
vector<int> f(n);
function<int(int)> dfs = [&](int i) -> int {
if (i >= n) return 0;
if (f[i]) return f[i];
int ans = inf;
for (int j = i; j < n; ++j) {
if (__gcd(nums[i], nums[j]) > 1) {
ans = min(ans, 1 + dfs(j + 1));
}
}
f[i] = ans;
return ans;
};
int ans = dfs(0);
return ans < inf ? ans : -1;
}
};

• class Solution:
def validSubarraySplit(self, nums: List[int]) -> int:
@cache
def dfs(i):
if i >= n:
return 0
ans = inf
for j in range(i, n):
if gcd(nums[i], nums[j]) > 1:
ans = min(ans, 1 + dfs(j + 1))
return ans

n = len(nums)
ans = dfs(0)
dfs.cache_clear()
return ans if ans < inf else -1


• func validSubarraySplit(nums []int) int {
n := len(nums)
f := make([]int, n)
var dfs func(int) int
const inf int = 0x3f3f3f3f
dfs = func(i int) int {
if i >= n {
return 0
}
if f[i] > 0 {
return f[i]
}
ans := inf
for j := i; j < n; j++ {
if gcd(nums[i], nums[j]) > 1 {
ans = min(ans, 1+dfs(j+1))
}
}
f[i] = ans
return ans
}
ans := dfs(0)
if ans < inf {
return ans
}
return -1
}

func min(a, b int) int {
if a < b {
return a
}
return b
}

func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}