LeetCode 2436 - Minimum Split Into Subarrays With GCD Greater Than One

The problem requires splitting a given array of positive integers into contiguous subarrays such that the greatest common divisor (GCD) of each subarray is strictly greater than 1. The goal is to minimize the number of subarrays after splitting.

leetcodemediumarraymathdynamic-programminggreedynumber-theory

LeetCode Problem 2436

Difficulty: 🟡 Medium
Topics: Array, Math, Dynamic Programming, Greedy, Number Theory

Solution

Problem Understanding

The problem requires splitting a given array of positive integers into contiguous subarrays such that the greatest common divisor (GCD) of each subarray is strictly greater than 1. The goal is to minimize the number of subarrays after splitting.

In simpler terms, we need to partition the array into the fewest contiguous segments where each segment shares at least one common factor greater than 1. The input is an array nums with length up to 2000 and elements up to $10^9$. The output is a single integer representing the minimal number of subarrays that satisfy the GCD condition.

Important constraints and observations:

  • Each element is ≥ 2, so every single element has a GCD ≥ 2 if taken alone.
  • A naive approach of considering every possible split would be too slow due to the exponential number of subarray combinations.
  • Edge cases include arrays where all elements share a common factor (only one subarray needed) and arrays where consecutive elements are co-prime (every element may need to be its own subarray).

Approaches

The brute-force approach would try every possible split of the array and compute the GCD for each subarray. For each split, if all subarrays have GCD > 1, it keeps track of the minimum number of subarrays. While correct, this approach is infeasible because the number of splits grows exponentially with the array length, leading to time complexity $O(2^n \cdot n)$.

The key insight for an optimal solution is based on dynamic programming or a greedy approach using the property of GCD:

  1. Iterate through the array from left to right, maintaining the current GCD of the ongoing subarray.
  2. If adding the next element results in a GCD of 1, it means we cannot extend the current subarray any further. At that point, we split and start a new subarray.
  3. If adding the next element keeps the GCD > 1, continue extending the current subarray.

This works because GCD is associative and monotonic in this context: if the GCD of a subarray becomes 1, any further extension cannot fix it to be >1.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * n) O(n) Tries all splits, computes GCD each time
Optimal O(n) O(1) Single pass maintaining current GCD, split whenever GCD=1

Algorithm Walkthrough

  1. Initialize a variable splits = 1 to count the number of subarrays. Start with the first element as the current subarray.

  2. Initialize current_gcd as the first element of the array.

  3. Iterate through the array from the second element onward:

  4. Update current_gcd = gcd(current_gcd, nums[i]).

  5. If current_gcd becomes 1:

  6. Increment splits by 1 because we need a new subarray starting from nums[i].

  7. Reset current_gcd = nums[i] for the new subarray.

  8. Continue this process until the end of the array.

  9. Return splits as the minimum number of subarrays.

Why it works:

The algorithm ensures that each subarray has a GCD > 1. By maintaining a running GCD and splitting whenever it becomes 1, we guarantee minimal splits because we only split when absolutely necessary. This exploits the property that adding elements to a subarray whose GCD is already 1 cannot improve the GCD.

Python Solution

from typing import List
from math import gcd

class Solution:
    def minimumSplits(self, nums: List[int]) -> int:
        splits = 1
        current_gcd = nums[0]
        
        for num in nums[1:]:
            current_gcd = gcd(current_gcd, num)
            if current_gcd == 1:
                splits += 1
                current_gcd = num
        
        return splits

Implementation Explanation:

We start counting splits from 1 because the first element always forms a subarray. current_gcd tracks the GCD of the current subarray. As we iterate, we update current_gcd with the new element. If it becomes 1, the subarray cannot be extended further, so we increment splits and start a new subarray from the current element.

Go Solution

import "math"

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

func minimumSplits(nums []int) int {
    splits := 1
    currentGCD := nums[0]
    
    for i := 1; i < len(nums); i++ {
        currentGCD = gcd(currentGCD, nums[i])
        if currentGCD == 1 {
            splits++
            currentGCD = nums[i]
        }
    }
    
    return splits
}

Go-Specific Notes:

We implement gcd manually since Go does not have a standard library GCD function. Integer arithmetic suffices as the problem constraints guarantee all numbers are within bounds. Slices are used for iteration, and initialization of splits follows the same logic as Python.

Worked Examples

Example 1: nums = [12,6,3,14,8]

Step current_gcd splits Explanation
12 12 1 Start first subarray
6 gcd(12,6)=6 1 Continue subarray
3 gcd(6,3)=3 1 Continue subarray
14 gcd(3,14)=1 2 Split, new subarray starts with 14
8 gcd(14,8)=2 2 Continue subarray

Output = 2

Example 2: nums = [4,12,6,14]

Step current_gcd splits Explanation
4 4 1 Start first subarray
12 gcd(4,12)=4 1 Continue subarray
6 gcd(4,6)=2 1 Continue subarray
14 gcd(2,14)=2 1 Continue subarray

Output = 1

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through the array, each gcd operation is O(log(max(nums))) but bounded by constant factors for practical constraints
Space O(1) Only two variables are maintained: splits and current_gcd

The linear pass ensures efficiency for arrays up to length 2000.

Test Cases

# Provided examples
assert Solution().minimumSplits([12,6,3,14,8]) == 2  # Split necessary
assert Solution().minimumSplits([4,12,6,14]) == 1    # All elements share factor >1

# Boundary and edge cases
assert Solution().minimumSplits([2]) == 1             # Single element
assert Solution().minimumSplits([2,3,5,7]) == 4      # All primes, each must be separate
assert Solution().minimumSplits([6,9,15,10]) == 2    # Mixed factors
assert Solution().minimumSplits([8,16,32,64]) == 1   # All divisible by 2
assert Solution().minimumSplits([6,10,15]) == 3      # Consecutive co-primes
Test Why
[12,6,3,14,8] GCD splits into two subarrays
[4,12,6,14] Entire array can be one subarray
[2] Single element edge case
[2,3,5,7] All co-prime, each element must be separate
[6,9,15,10] Mixed factors, demonstrates partial splits
[8,16,32,64] Uniform factors, minimal split
[6,10,15] No common GCD >1 for any two consecutive, maximal split

Edge Cases

  1. Single Element Array: For nums = [2], the algorithm correctly returns 1 because a single element already has GCD >1. Naive approaches that expect at least two elements could fail.
  2. All Elements Co-prime: For arrays of primes like [2,3,5,7], each element needs its own subarray. The algorithm splits whenever the GCD becomes 1.
  3. Uniform Factor Array: Arrays like [8,16,32] are all divisible by 2. The algorithm correctly keeps them as a single subarray since the running GCD never drops to 1. This verifies that unnecessary splits are avoided.

This approach balances correctness, efficiency, and simplicity while directly leveraging GCD properties for minimal splits.