Question

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:
  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

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;
  }
};

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;
}