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)$.
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|