# 2436. Minimum Split Into Subarrays With GCD Greater Than One

## Description

You are given an array nums consisting of positive integers.

Split the array into one or more disjoint subarrays such that:

• Each element of the array belongs to exactly one subarray, and
• The GCD of the elements of each subarray is strictly greater than 1.

Return the minimum number of subarrays that can be obtained after the split.

Note that:

• The GCD of a subarray is the largest positive integer that evenly divides all the elements of the subarray.
• A subarray is a contiguous part of the array.

Example 1:

Input: nums = [12,6,3,14,8]
Output: 2
Explanation: We can split the array into the subarrays: [12,6,3] and [14,8].
- The GCD of 12, 6 and 3 is 3, which is strictly greater than 1.
- The GCD of 14 and 8 is 2, which is strictly greater than 1.
It can be shown that splitting the array into one subarray will make the GCD = 1.


Example 2:

Input: nums = [4,12,6,14]
Output: 1
Explanation: We can split the array into only one subarray, which is the whole array.


Constraints:

• 1 <= nums.length <= 2000
• 2 <= nums[i] <= 109

## Solutions

Solution 1: Greedy + Mathematics

For each element in the array, if its greatest common divisor (gcd) with the previous element is $1$, then it needs to be the first element of a new subarray. Otherwise, it can be placed in the same subarray with the previous elements.

Therefore, we first initialize a variable $g$, representing the gcd of the current subarray. Initially, $g=0$ and the answer variable $ans=1$.

Next, we traverse the array from front to back, maintaining the gcd $g$ of the current subarray. If the gcd of the current element $x$ and $g$ is $1$, then we need to make the current element the first element of a new subarray. Therefore, the answer increases by $1$, and $g$ is updated to $x$. Otherwise, the current element can be placed in the same subarray with the previous elements. Continue to traverse the array until the traversal ends.

The time complexity is $O(n \times \log m)$, where $n$ and $m$ are the length of the array and the maximum value in the array, respectively. The space complexity is $O(1)$.

• class Solution {
public int minimumSplits(int[] nums) {
int ans = 1, g = 0;
for (int x : nums) {
g = gcd(g, x);
if (g == 1) {
++ans;
g = x;
}
}
return ans;
}

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

• class Solution {
public:
int minimumSplits(vector<int>& nums) {
int ans = 1, g = 0;
for (int x : nums) {
g = gcd(g, x);
if (g == 1) {
++ans;
g = x;
}
}
return ans;
}
};

• class Solution:
def minimumSplits(self, nums: List[int]) -> int:
ans, g = 1, 0
for x in nums:
g = gcd(g, x)
if g == 1:
ans += 1
g = x
return ans


• func minimumSplits(nums []int) int {
ans, g := 1, 0
for _, x := range nums {
g = gcd(g, x)
if g == 1 {
ans++
g = x
}
}
return ans
}

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

• function minimumSplits(nums: number[]): number {
let ans = 1;
let g = 0;
for (const x of nums) {
g = gcd(g, x);
if (g == 1) {
++ans;
g = x;
}
}
return ans;
}

function gcd(a: number, b: number): number {
return b ? gcd(b, a % b) : a;
}