Minimum Subarrays in a Valid Split - Practice Coding Problems

Minimum Subarrays in a Valid Split - Problem

You are given an integer array nums. Splitting of an integer array nums into subarrays is valid if:

The greatest common divisor of the first and last elements of each subarray is greater than 1, and
Each element of nums belongs to exactly one subarray.

Return the minimum number of subarrays in a valid subarray splitting of nums. If a valid subarray splitting is not possible, return -1.

Note that:

The greatest common divisor of two numbers is the largest positive integer that evenly divides both numbers.
A subarray is a contiguous non-empty part of an array.

Input & Output

Example 1 — Basic Valid Split

$ Input: nums = [4,6,15,35]

› Output: 2

💡 Note: Split into [4,6] and [15,35]. GCD(4,6)=2>1 and GCD(15,35)=5>1, both valid.

Example 2 — Single Element Subarrays

$ Input: nums = [6,2,3,4]

› Output: 4

💡 Note: Each element forms its own subarray: [6], [2], [3], [4]. GCD of single element with itself is the element itself, all > 1.

Example 3 — Impossible Split

$ Input: nums = [1,2,3,4,5]

› Output: -1

💡 Note: First element is 1. Since GCD(1,x)=1 for any x, no valid subarray starting with 1 can have GCD>1.

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array [4,6,15,35] to split into valid subarrays

Check GCD

Each subarray must have GCD(first,last) > 1

Minimum Split

Find minimum number of subarrays needed

Key Takeaway

🎯 Key Insight: If first element is 1, splitting is impossible since GCD(1,x)=1 always

Asked in

G Google 35 M Microsoft 28 a Amazon 22

The key insight is that if the first element is 1, no valid split exists since GCD(1,x)=1. Otherwise, use dynamic programming to find minimum subarrays where each has GCD(first,last)>1. Best approach is memoized DP with Time: O(n³), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Approach	O(n²)	O(1)	Extend each subarray as far as possible before starting a new one
Recursive Backtracking	O(2ⁿ)	O(n)	Try all possible ways to split the array into valid subarrays
Dynamic Programming with Memoization	O(n³)	O(n)	Cache results of subproblems to avoid recomputation

Greedy Approach — Algorithm Steps

Start with first element
Extend subarray as far as possible with valid GCD
When can't extend further, start new subarray
Count total subarrays needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with first element as start of subarray

Extend

Keep extending while GCD(first, current) > 1

Split

When can't extend further, start new subarray

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int solution(int* nums, int size) {
    int count = 0;
    int i = 0;
    
    while (i < size) {
        int start = i;
        // Try to extend current subarray as far as possible
        while (i < size && gcd(nums[start], nums[i]) > 1) {
            i++;
        }
        
        // If we couldn't move from start, no valid split possible
        if (i == start) {
            return -1;
        }
        
        count++;
    }
    
    return count;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[100];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each position, we may check GCD with all following elements

⚠ Quadratic Growth

Space Complexity

O(1)

Only using a few variables, no extra data structures

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler