Problem Description

You have an array nums containing only positive integers. Your task is to split this array into the minimum number of contiguous subarrays where each subarray must satisfy a specific condition about its GCD (Greatest Common Divisor).

The splitting rules are:

• Every element from the original array must belong to exactly one subarray
• For each subarray you create, the GCD of all elements in that subarray must be strictly greater than 1
• The subarrays must be contiguous (you cannot rearrange elements)

The GCD of a subarray is the largest positive integer that divides all elements in that subarray evenly. For example, the GCD of [6, 12, 18] is 6, while the GCD of [4, 6, 8] is 2.

Your goal is to find the minimum number of such subarrays needed to partition the entire array while satisfying the GCD constraint.

For example, if you have an array [12, 6, 3, 14, 8], you might split it into [12, 6, 3] (GCD = 3) and [14, 8] (GCD = 2), resulting in 2 subarrays. Each subarray has a GCD greater than 1, and you've used the minimum number of splits possible.

Intuition

The key insight is to be greedy and try to extend each subarray as long as possible while maintaining a GCD greater than 1.

Think about it this way: when we're building a subarray from left to right, we want to include as many elements as possible in the current subarray before we're forced to start a new one. The only time we're forced to start a new subarray is when adding the next element would make the GCD become 1.

Why does this greedy approach work? Because if we can maintain a GCD greater than 1 by including more elements, there's no benefit to splitting earlier - we'd just create more subarrays unnecessarily.

The mathematical property we leverage is that the GCD of a set of numbers can only decrease or stay the same as we add more numbers - it never increases. Starting with any number, its GCD with 0 is itself (by convention, gcd(0, x) = x). As we add more numbers, we compute gcd(current_gcd, new_number).

The critical moment is when the running GCD becomes 1. At this point, no matter what additional numbers we add, the GCD will remain 1 (since 1 divides everything). This violates our constraint, so we must start a new subarray at this point.

The algorithm naturally emerges: maintain a running GCD for the current subarray. When it becomes 1, we know we've gone too far - the current element cannot be part of the previous subarray. So we increment our subarray count and start fresh with the current element as the beginning of a new subarray.

This greedy strategy ensures we use the minimum number of subarrays because we only split when absolutely necessary - when continuing would violate the GCD > 1 constraint.

Learn more about Greedy, Math and Dynamic Programming patterns.

Solution Approach

The implementation follows a straightforward greedy traversal of the array while maintaining the running GCD of the current subarray.

We initialize two variables:

• ans = 1: The answer counter starting at 1 (since we need at least one subarray)
• g = 0: The running GCD of the current subarray, initialized to 0

The choice of initializing g = 0 is clever because of the mathematical property that gcd(0, x) = x for any positive integer x. This means when we encounter the first element, the GCD will simply become that element.

For each element x in the array:

1. Calculate the new GCD: g = gcd(g, x)
2. Check if the GCD has become 1:
   • If g == 1, this means we cannot include x in the current subarray (as it would violate the GCD > 1 constraint)
   • Start a new subarray: increment ans += 1
   • Reset the GCD for the new subarray: g = x (the current element becomes the first element of the new subarray)
3. If g != 1, we can safely include x in the current subarray and continue

The algorithm processes each element exactly once in a single pass, making it very efficient.

Let's trace through an example with nums = [6, 12, 3, 14, 8]:

• Start: ans = 1, g = 0
• Element 6: g = gcd(0, 6) = 6, continue
• Element 12: g = gcd(6, 12) = 6, continue
• Element 3: g = gcd(6, 3) = 3, continue
• Element 14: g = gcd(3, 14) = 1, split needed! ans = 2, g = 14
• Element 8: g = gcd(14, 8) = 2, continue
• Result: 2 subarrays [6, 12, 3] and [14, 8]

The time complexity is O(n × log(max(nums))) where the log factor comes from the GCD calculation, and space complexity is O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through the algorithm with the array nums = [12, 6, 3, 14, 8].

Initial Setup:

• ans = 1 (we need at least one subarray)
• g = 0 (running GCD, starts at 0)

Step 1: Process element 12

• Calculate: g = gcd(0, 12) = 12
• Since g = 12 > 1, we can include 12 in the current subarray
• Current subarray: [12]

Step 2: Process element 6

• Calculate: g = gcd(12, 6) = 6
• Since g = 6 > 1, we can include 6 in the current subarray
• Current subarray: [12, 6]

Step 3: Process element 3

• Calculate: g = gcd(6, 3) = 3
• Since g = 3 > 1, we can include 3 in the current subarray
• Current subarray: [12, 6, 3]

Step 4: Process element 14

• Calculate: g = gcd(3, 14) = 1
• Since g = 1, we cannot include 14 in the current subarray!
• We must start a new subarray:
  • Increment: ans = 2
  • Reset: g = 14 (14 becomes the first element of the new subarray)
• First subarray complete: [12, 6, 3] with GCD = 3
• New current subarray: [14]

Step 5: Process element 8

• Calculate: g = gcd(14, 8) = 2
• Since g = 2 > 1, we can include 8 in the current subarray
• Current subarray: [14, 8]

Final Result:

• Total subarrays needed: ans = 2
• The array splits into: [12, 6, 3] (GCD = 3) and [14, 8] (GCD = 2)
• Both subarrays satisfy the constraint of having GCD > 1

The greedy approach successfully minimizes the number of subarrays by only splitting when absolutely necessary (when the GCD would become 1).

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log m), where n is the length of the array and m is the maximum value in the array. This is because:

• The algorithm iterates through the array once, which takes O(n) time
• For each element, it computes the GCD using the gcd(g, x) function
• The GCD computation between two numbers has a time complexity of O(log m) where m is the maximum of the two numbers being compared
• Therefore, the overall time complexity is O(n × log m)

The space complexity is O(1) as the algorithm only uses a constant amount of extra space regardless of the input size. The variables ans, g, and x are the only additional storage used, and they don't scale with the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrectly Handling Arrays with All Elements Having GCD = 1

A critical edge case occurs when the entire array consists of numbers that are pairwise coprime (their GCD is 1). For example, consider nums = [2, 3, 5, 7] where all elements are prime numbers.

The Problem:

• When processing element 2: g = gcd(0, 2) = 2
• When processing element 3: g = gcd(2, 3) = 1 → Split! ans = 2, g = 3
• When processing element 5: g = gcd(3, 5) = 1 → Split! ans = 3, g = 5
• When processing element 7: g = gcd(5, 7) = 1 → Split! ans = 4, g = 7

This results in 4 subarrays: [2], [3], [5], [7]. However, each single-element subarray has a GCD equal to itself. If any element equals 1, that subarray would violate the GCD > 1 constraint!

Solution: Before running the algorithm, check if any element in the array equals 1. If so, return -1 or handle it as an impossible case:

def minimumSplits(self, nums: List[int]) -> int:
    # Check for impossible case
    if 1 in nums:
        return -1  # Cannot form valid subarrays if any element is 1
  
    num_splits = 1
    current_gcd = 0
  
    for num in nums:
        current_gcd = gcd(current_gcd, num)
        if current_gcd == 1:
            num_splits += 1
            current_gcd = num
  
    return num_splits

Pitfall 2: Misunderstanding GCD Initialization with Zero

Developers might be confused about why current_gcd is initialized to 0 instead of the first element, potentially leading to incorrect implementations like:

# Incorrect approach
current_gcd = nums[0]  # Wrong initialization
for i in range(1, len(nums)):  # Skipping first element
    current_gcd = gcd(current_gcd, nums[i])
    # ... rest of logic

The Problem: This approach requires special handling for empty arrays or single-element arrays and makes the code more complex.

Solution: Stick with current_gcd = 0 initialization. The mathematical property gcd(0, x) = x elegantly handles the first element without special cases. This makes the code cleaner and works uniformly for all array sizes:

current_gcd = 0  # Correct initialization
for num in nums:  # Process ALL elements uniformly
    current_gcd = gcd(current_gcd, num)
    # ... rest of logic

Pitfall 3: Off-by-One Error in Answer Initialization

Some might initialize the answer counter to 0 instead of 1, thinking in terms of "number of splits" rather than "number of subarrays":

# Incorrect
num_splits = 0  # Wrong! This counts split points, not subarrays

The Problem: If you start with 0, you're counting the number of times you split, not the number of resulting subarrays. An array split k times results in k+1 subarrays.

Solution: Always initialize to 1 since you start with at least one subarray:

num_splits = 1  # Correct! We start with one subarray

Alternatively, if you prefer counting split points, remember to add 1 to the final result:

split_points = 0
# ... algorithm logic incrementing split_points
return split_points + 1  # Convert splits to number of subarrays