Problem Description
Given an integer array nums, split the array into contiguous subarrays such that for each subarray the greatest common divisor (gcd) of its first and last elements is greater than 1. Each element must belong to exactly one subarray. Return the MINIMUM number of subarrays required to achieve a valid split. If no valid split exists, return -1.
Key Insights
- A subarray (segment) is valid if gcd(first_element, last_element) > 1.
- Splitting at a single element is always valid if that element is >1 (since gcd(x, x) = x > 1); however, if an element is 1, it might force a split because gcd(1, any) equals 1.
- Use dynamic programming (DP): Let dp[i] be the minimum number of valid subarrays for nums[0...i-1].
- For every potential split ending at index i-1, check every previous index j such that the segment nums[j...i-1] is valid (gcd(nums[j], nums[i-1]) > 1) and update dp[i] = min(dp[i], dp[j] + 1).
- The problem constraints (nums.length <= 1000) allow an O(n²) solution with gcd calculations.
Space and Time Complexity
Time Complexity: O(n² * log(max(nums))) – Two nested loops over the array with a gcd computation (which runs in O(log(max(nums)))). Space Complexity: O(n) – DP array used for storing the minimum subarray splits.
Solution
We solve the problem using a dynamic programming approach. The idea is to iterate over each possible ending index i of a subarray (from 1 to n) and then for each i check every possible starting index j where the subarray nums[j...i-1] is valid (i.e. gcd(nums[j], nums[i-1]) > 1). We update our DP array accordingly. The key observation is that the only check we need for a subarray is to compute the gcd of its first and last elements; intermediate elements do not affect this condition.