Minimum split into subarrays with gcd greater than one

Array Math Dynamic Programming Greedy Number Theory

70.2% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_splits(nums: Vec<i32>) -> i32 {
    let mut count = 1;
    let mut g = nums[0];
    for i in 1..nums.len() {
      g = Self::gcd(g, nums[i]);
      if g == 1 {
        count += 1;
        g = nums[i];
      }
    }
    count
  }

  fn gcd(a: i32, b: i32) -> i32 {
    if b == 0 { a } else { Self::gcd(b, a % b) }
  }
}