Minimum subarrays in a valid split

Array Math Dynamic Programming Number Theory

64.7% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn valid_subarray_split(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    let mut dp = vec![i32::MAX; n + 1];
    dp[0] = 0;
    for i in 0..n {
      if dp[i] == i32::MAX { continue; }
      for j in i..n {
        if Self::gcd(nums[i], nums[j]) > 1 {
          dp[j + 1] = dp[j + 1].min(dp[i] + 1);
        }
      }
    }
    if dp[n] == i32::MAX { -1 } else { dp[n] }
  }

  fn gcd(a: i32, b: i32) -> i32 {
    if b == 0 { a } else { Self::gcd(b, a % b) }
  }
}