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

[{"language":"C++","code":"#include <numeric>\nclass Solution {\npublic:\n    int minimumSubarrays(vector<int>& nums) {\n        int n = nums.size();\n        vector<int> dp(n, 1e9);\n        for (int i = 0; i < n; ++i) {\n            for (int j = 0; j <= i; ++j) {\n                if (gcd(nums[j], nums[i]) > 1) {\n                    dp[i] = min(dp[i], (j ? dp[j-1] : 0) + 1);\n                }\n            }\n        }\n        return dp[n-1] >= 1e9 ? -1 : dp[n-1];\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">#include</span><span style=\"color:#032F62;--shiki-dark:#9ECBFF\"> &#x3C;numeric></span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> minimumSubarrays</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> nums</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;-

Related Tags