Teaching Kids Programming – Minimum Split Into Subarrays With GCD Greater Than One (Greedy Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

Greedy Algorithm to Find the Minimum Split Into Subarrays With GCD Greater Than One

We can apply the greedy strategy here, if the next number does not bring the GCD (Greatest Common Divisor) of current group to one, then we might just include it. Otherwise, we can start a new group from the next number.

1
2
3
4
5
6
7
8
9

class Solution:
    def minimumSplits(self, nums: List[int]) -> int:
        ans, cur = 0, 1
        for i, j in enumerate(nums):
            cur = gcd(cur, j)
            if cur == 1:
                ans += 1
                cur = j
        return ans

class Solution:
    def minimumSplits(self, nums: List[int]) -> int:
        ans, cur = 0, 1
        for i, j in enumerate(nums):
            cur = gcd(cur, j)
            if cur == 1:
                ans += 1
                cur = j
        return ans

The space complexity is O(1) constant, and the time complexity is as the GCD(a, b) takes log(a, b) time.

–EOF (The Ultimate Computing & Technology Blog) —