Minimum Split Into Subarrays With GCD Greater Than One

Problem

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.

Examples

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] <= 10^9

Solution

Method 1 – Greedy Partitioning by GCD

Intuition

We want to split the array into the minimum number of contiguous subarrays such that the GCD of each subarray is strictly greater than 1. We can greedily extend each subarray as far as possible, starting a new subarray only when the GCD drops to 1.

Approach

Iterate through the array, maintaining the current GCD. If adding the next element causes the GCD to become 1, start a new subarray. Count the number of subarrays.

Code

C++

#include <numeric>
class Solution {
public:
    int minimumSplits(vector<int>& nums) {
        int ans = 1, cur = nums[0];
        for (int i = 1; i < nums.size(); ++i) {
            cur = gcd(cur, nums[i]);
            if (cur == 1) {
                ans++;
                cur = nums[i];
            }
        }
        return ans;
    }
};

Go

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}
func minimumSplits(nums []int) int {
    ans, cur := 1, nums[0]
    for i := 1; i < len(nums); i++ {
        cur = gcd(cur, nums[i])
        if cur == 1 {
            ans++
            cur = nums[i]
        }
    }
    return ans
}

Java

class Solution {
    private int gcd(int a, int b) {
        while (b != 0) {
            int t = b; b = a % b; a = t;
        }
        return a;
    }
    public int minimumSplits(int[] nums) {
        int ans = 1, cur = nums[0];
        for (int i = 1; i < nums.length; i++) {
            cur = gcd(cur, nums[i]);
            if (cur == 1) {
                ans++;
                cur = nums[i];
            }
        }
        return ans;
    }
}

Kotlin

class Solution {
    private fun gcd(a: Int, b: Int): Int {
        var x = a; var y = b
        while (y != 0) { val t = y; y = x % y; x = t }
        return x
    }
    fun minimumSplits(nums: IntArray): Int {
        var ans = 1; var cur = nums[0]
        for (i in 1 until nums.size) {
            cur = gcd(cur, nums[i])
            if (cur == 1) {
                ans++
                cur = nums[i]
            }
        }
        return ans
    }
}

Python

from math import gcd
class Solution:
    def minimumSplits(self, nums: list[int]) -> int:
        ans, cur = 1, nums[0]
        for num in nums[1:]:
            cur = gcd(cur, num)
            if cur == 1:
                ans += 1
                cur = num
        return ans

Rust

impl Solution {
    pub fn minimum_splits(nums: Vec<i32>) -> i32 {
        fn gcd(mut a: i32, mut b: i32) -> i32 {
            while b != 0 { let t = b; b = a % b; a = t; } a
        }
        let mut ans = 1;
        let mut cur = nums[0];
        for &num in &nums[1..] {
            cur = gcd(cur, num);
            if cur == 1 {
                ans += 1;
                cur = num;
            }
        }
        ans
    }
}

TypeScript

function gcd(a: number, b: number): number {
    while (b !== 0) { let t = b; b = a % b; a = t; } return a;
}
class Solution {
    minimumSplits(nums: number[]): number {
        let ans = 1, cur = nums[0];
        for (let i = 1; i < nums.length; i++) {
            cur = gcd(cur, nums[i]);
            if (cur === 1) {
                ans++;
                cur = nums[i];
            }
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n) — One pass through the array.
• 🧺 Space complexity: O(1) — Only a few variables.