We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Split Into Subarrays With GCD Greater Than One

Number: 2579

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given an array of positive integers, split the array into one or more contiguous subarrays such that every subarray has a GCD (greatest common divisor) strictly greater than 1. Return the minimum number of subarrays needed to achieve this.

Key Insights

  • A single element always has a GCD equal to itself (and since each nums[i] ≥ 2, a single-element subarray is valid).
  • The challenge is to group contiguous elements such that the GCD of the group exceeds 1.
  • Use dynamic programming where dp[i] represents the minimum splits for the prefix ending at index i-1.
  • While iterating backwards from a given index, maintain the running GCD; if it remains above 1, update dp for the current segment.
  • Once the running GCD falls to 1, further extension will never improve it (since adding more numbers cannot restore the GCD to above 1), so break early from the inner loop for efficiency.

Space and Time Complexity

Time Complexity: O(n² * log(max(nums))) — The outer loop runs for n elements and the inner loop can run up to n iterations with GCD computation taking O(log(max(nums))). Space Complexity: O(n) — Only an extra dp array of size n+1 is used.

Solution

The solution uses a dynamic programming approach:

  1. Create a dp array where dp[i] represents the minimum number of subarrays needed for the first i elements.
  2. Initialize dp[0] = 0.
  3. For every index i in the array, iterate backwards updating the current GCD for the subarray ending at i.
  4. If at a certain point the current GCD is more than 1, update dp[i+1] = min(dp[i+1], dp[j] + 1) where j is the start index of the subarray.
  5. Stop the inner loop early if the current GCD becomes 1.
  6. The answer is dp[n] where n is the length of the array.

Data Structures and Algorithms Used:

  • Dynamic Programming: to record and update the minimum splits needed.
  • Iterative GCD computation: using the Euclidean algorithm for efficiently computing the GCD.
  • Greedy early exit in the inner loop when further extension is non-beneficial.

Code Solutions

# Python solution for splitting array into subarrays with GCD > 1

def minSplit(nums):
    n = len(nums)
    # dp[i] holds the minimum number of splits for the first i elements
    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    from math import gcd
    # Process each element as the end of a subarray
    for i in range(n):
        current_gcd = 0
        # Iterate backwards trying to form a valid subarray ending at i
        for j in range(i, -1, -1):
            current_gcd = gcd(nums[j], current_gcd)
            if current_gcd > 1:
                dp[i + 1] = min(dp[i + 1], dp[j] + 1)
            else:
                # When the running GCD becomes 1, further extension won't improve it
                break
    return dp[n]

# Test cases
print(minSplit([12, 6, 3, 14, 8]))  # Expected output: 2
print(minSplit([4, 12, 6, 14]))     # Expected output: 1
← Back to All Questions