Skip to main content
Talentd

Minimum Split Into Subarrays With GCD Greater Than One - Solution & Explanation

MediumPremiumFree on FleetCodeArrayMathDynamic ProgrammingGreedy10 min read
Practice this problem

Problem Statement

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] <= 109

Approach Overview

Problem Overview: Given an integer array, split it into the minimum number of contiguous subarrays such that the gcd of every subarray is strictly greater than 1. If a segment’s GCD becomes 1, that segment is invalid and must be split earlier.

Approach 1: Dynamic Programming with GCD Tracking (O(n^2 log A) time, O(n) space)

Define dp[i] as the minimum splits needed for the prefix ending at index i. For each position, iterate backward and continuously compute the GCD of the current segment using gcd(g, nums[j]). As long as the GCD remains greater than 1, update dp[i] from dp[j-1]. Once the GCD becomes 1, extending the segment further is useless. This approach demonstrates the core idea of segment GCD validity but becomes expensive because each index may scan many previous elements.

Approach 2: Greedy + Mathematics (O(n log A) time, O(1) space)

Traverse the array while maintaining the GCD of the current subarray. Start with the first number and keep updating current_gcd = gcd(current_gcd, nums[i]). If the GCD stays greater than 1, the current segment remains valid and you continue extending it. When the GCD becomes 1, the current segment can no longer satisfy the requirement. Split right before this element, increment the segment count, and restart the segment with nums[i] as the new base. Each element participates in a constant number of GCD operations, making the solution linear with a logarithmic factor from the GCD calculation.

This greedy logic works because once the running GCD drops to 1, adding more elements can never increase it back above 1. The only valid move is to start a new subarray immediately.

Key concepts come from array traversal, number theory (GCD properties), and optimization ideas often seen in dynamic programming problems.

Recommended for interviews: Greedy + Mathematics. Interviewers expect you to recognize the monotonic property of GCD: once it reaches 1, it cannot recover. The DP formulation shows understanding of the state definition, but the greedy observation demonstrates stronger algorithmic intuition and reduces complexity to O(n log A).

Solution

For each element in the array, if its greatest common divisor (gcd) with the previous element is 1, then it needs to be the first element of a new subarray. Otherwise, it can be placed in the same subarray with the previous elements.

Therefore, we first initialize a variable g, representing the gcd of the current subarray. Initially, g=0 and the answer variable ans=1.

Next, we traverse the array from front to back, maintaining the gcd g of the current subarray. If the gcd of the current element x and g is 1, then we need to make the current element the first element of a new subarray. Therefore, the answer increases by 1, and g is updated to x. Otherwise, the current element can be placed in the same subarray with the previous elements. Continue to traverse the array until the traversal ends.

The time complexity is O(n times log m), where n and m are the length of the array and the maximum value in the array, respectively. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with GCD TrackingO(n^2 log A)O(n)Useful for understanding the state transition and exploring all valid segment boundaries
Greedy + Mathematics (Running GCD)O(n log A)O(1)Best general solution; optimal for large arrays with simple linear traversal

Video Solution

leetcode 2436. Minimum Split Into Subarrays With GCD Greater Than One - gcd and check • Code-Yao • 195 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Minimum Split Into Subarrays With GCD Greater Than One easy or hard?
The problem is rated Medium on LeetCode with around a 70% acceptance rate. The implementation is straightforward once you recognize the key observation that a running GCD cannot increase after reaching 1, enabling a greedy segmentation strategy.
Minimum Split Into Subarrays With GCD Greater Than One Python/Java solution
Implement a single pass through the array while tracking the current segment's GCD. Use the built-in gcd function (such as math.gcd in Python or Math.gcd equivalents in Java/C++ libraries). When the GCD becomes 1, increment the split counter and reset the running GCD to the current element.
How to solve Minimum Split Into Subarrays With GCD Greater Than One in O(n)?
A near-linear solution uses a greedy scan with a running GCD. Keep extending the current subarray while the GCD stays greater than 1. When the GCD becomes 1, increment the split count and restart the segment from the current element. The algorithm performs one pass over the array with GCD updates, giving O(n log A) complexity in practice.
What is the best approach for Minimum Split Into Subarrays With GCD Greater Than One?
The optimal approach is Greedy with running GCD computation. Traverse the array and maintain the GCD of the current segment. If the GCD becomes 1, split before the current element and start a new segment. This works because GCD is monotonic when adding elements and cannot increase once it reaches 1. The time complexity is O(n log A).
Is Minimum Split Into Subarrays With GCD Greater Than One asked at Google/Amazon/Meta?
Problems involving GCD properties, greedy segmentation, and number theory appear frequently in interviews at companies like Google, Amazon, and Meta. Variants that require maintaining a running GCD or splitting arrays based on mathematical constraints are common interview patterns.
What data structure is used in Minimum Split Into Subarrays With GCD Greater Than One?
The greedy solution mainly relies on simple array traversal and repeated GCD calculations using the Euclidean algorithm. No advanced data structures are required, which keeps the space complexity constant at O(1).
What is the time complexity of Minimum Split Into Subarrays With GCD Greater Than One?
The optimal greedy solution runs in O(n log A) time where n is the array length and A is the maximum value in the array. Each step performs a constant number of GCD computations, and the Euclidean algorithm takes O(log A). Space complexity is O(1).

Ready to solve this problem?

Practice Minimum Split Into Subarrays With GCD Greater Than One with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Subarrays in a Valid Split