2436. Minimum Split Into Subarrays With GCD Greater Than One

MediumGreedyArrayMathDynamic ProgrammingNumber Theory
Leetcode Link

Problem Description

The problem presents an array of positive integers and requires splitting this array into one or more disjoint subarrays. The split must be such that each element in the original array belongs to exactly one subarray. Additionally, for each subarray formed, the greatest common divisor (GCD) of its elements must be strictly greater than 1, meaning none of the subarrays should consist of elements that are only mutually prime. The objective is to find the minimum number of such subarrays that can be created following these rules.

Intuition

The intuition behind the solution is leveraged from the fact that the GCD of a subarray can only decrease or stay the same when more elements are added to it. Starting from the first element, we can try to extend the subarray as much as possible until the GCD becomes 1. When the GCD is 1, it means that adding any more elements would not allow us to maintain the condition that the GCD is greater than 1. Therefore, we start a new subarray beginning at that point.

The approach incrementally builds subarrays and keeps track of the current GCD. Whenever the GCD becomes 1, the subarray is finished, and a new one begins. The gcd function (presumably from [math](/problems/math-basics) module or a similar implementation) calculates the GCD of two numbers and is repeatedly used to update the current GCD of each forming subarray. If at any point the GCD of the cumulative elements is 1, a split is made (indicated by incrementing the answer), and the GCD is reset to the value of the current element, thereby starting a new subarray. This process is repeated for all elements in the array, and the final answer denotes the minimum number of subarrays formed.

The reason the starting value of ans is 1 in the solution is because at least one subarray is always possible, given that all the integers are positive and the array cannot be empty.

Learn more about Greedy, Math and Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Solution Approach

The solution uses a greedy approach, where we try to extend a subarray as much as possible before needing to create a new subarray so that the GCD of each subarray is greater than 1.

Here's a step by step breakdown of how the solution is implemented:

  1. Initialize ans, the counter for minimum subarrays, to 1 because we can always form at least one subarray.
  2. Initialize a variable g to 0, which will store the running GCD of the current subarray.
  3. Iterate over each number x in the array nums.
    • Calculate the new GCD of the current subarray by taking the GCD of g (the GCD so far) and x (the current number). The GCD is updated using the statement g = gcd(g, x).
    • If the GCD after adding x to the subarray becomes 1, then:
      • Increment ans by 1 as this signifies that a new subarray must start to fulfill the condition that each subarray must have a GCD greater than 1.
      • Also, reset g to the value of x because a new subarray is starting with x as its first element.
    • If the GCD does not become 1, it implies that x can be added to the current subarray without violating the condition, and we continue to the next iteration.
  4. After iterating through all elements, return the value of ans.

The Python gcd function used in the code can be brought in by importing it from the [math](/problems/math-basics) library (from math import gcd) or can be implemented if needed.

This algorithm does a single pass over the input array (O(n) time complexity, where n is the number of elements in the array) and only uses constant extra space (O(1) space complexity), making it efficient and suitable for large arrays as well.

By following this pattern, we can thus ensure that we always form subarrays with the maximum possible length without violating the GCD condition, which leads us to the minimum possible number of subarrays.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Example Walkthrough

Let's go through an example to illustrate the solution approach. Consider the array of positive integers [12, 6, 9, 3, 5, 7].

Following the steps outlined in the solution approach:

  1. Initialize ans to 1, as we can form at least one subarray.
  2. Initialize g to 0, to keep track of the GCD of the current subarray.

Proceed with the array elements:

  • For the first element 12, we calculate the GCD of g and 12. Since g is 0, the GCD is 12 (because the GCD of any number and 0 is the number itself). Now, g is updated to 12.
  • Moving to the second element 6, the new GCD is the GCD of 12 and 6, which is 6. We update g to 6.
  • The third element is 9. The GCD of 6 and 9 is 3, so g is updated to 3.
  • Next is the number 3. The GCD of 3 and 3 remains 3, so we continue building this subarray.
  • The fifth element is 5, and here the GCD of 3 and 5 is 1. Since the GCD has become 1, we need to start a new subarray. We increment ans to 2 and reset g to 5 (the current element).
  • The final element, 7, has a GCD of 1 with 5 (since 5 and 7 are prime with respect to each other), which would again imply the start of a new subarray. We increment ans to 3 and set g to 7.

Therefore, the minimum number of subarrays where each subarray has a GCD greater than 1 is 3. These are [12, 6, 9, 3], [5], and [7].

The example perfectly illustrates the efficiency and the greedy nature of the solution, where the algorithm tries to build the longest subarray possible before needing to start a new one due to encountering a GCD of 1.

Solution Implementation

1from math import gcd
2from typing import List
3
4class Solution:
5    def minimumSplits(self, nums: List[int]) -> int:
6        # Initialize the variables:
7        # 'split_count' to count the minimum splits needed
8        # 'current_gcd' to keep track of the gcd of the current group
9        split_count, current_gcd = 1, 0
10      
11        # Iterate over each number in the list
12        for number in nums:
13            # Calculate the gcd of the current group and the current number
14            current_gcd = gcd(current_gcd, number)
15          
16            # When the gcd becomes 1, it's optimal to split here
17            # because any next number can start a new group with gcd 1
18            if current_gcd == 1:
19                split_count += 1
20                current_gcd = number  # Start a new group with the current number
21          
22        # Return the minimum number of splits needed
23        return split_count
24
1class Solution {
2    // Method to calculate the minimum number of splits in the array
3    public int minimumSplits(int[] nums) {
4        int answer = 1; // Start with a single split
5        int currentGCD = 0; // Initialize GCD
6      
7        // Iterate through each number in the array
8        for (int number : nums) {
9            // Calculate the GCD of currentGCD and the current number
10            currentGCD = gcd(currentGCD, number);
11          
12            // If the GCD is 1, a new split is required
13            if (currentGCD == 1) {
14                answer++; // Increase the number of splits
15                currentGCD = number; // Reset the currentGCD to the current number
16            }
17        }
18        // Return the total number of splits required
19        return answer;
20    }
21
22    // Helper method to calculate the Greatest Common Divisor (GCD) of two numbers
23    private int gcd(int a, int b) {
24        // If second number is 0, the GCD is the first number
25        return b == 0 ? a : gcd(b, a % b); // Recursively calculate gcd
26    }
27}
28
1#include <vector> // Include the vector header for using the vector class
2
3class Solution {
4public:
5    int minimumSplits(std::vector<int>& nums) {
6        int splitsRequired = 1; // Start with a single split required
7        int currentGcd = 0; // Initialize gcd to 0 representing an empty subsequence
8
9        // Iterate over each number in the vector nums
10        for (int num : nums) {
11            // Update the current gcd to include the current number
12            currentGcd = std::gcd(currentGcd, num); 
13
14            // If the gcd is 1, we need to start a new subsequence
15            if (currentGcd == 1) {
16                ++splitsRequired; // Increment the number of splits required
17                currentGcd = num; // Start a new subsequence with the current number as the first element
18            }
19        }
20
21        return splitsRequired; // Return the total splits required
22    }
23};
24
1// Calculate the minimum number of splits required
2function minimumSplits(nums: number[]): number {
3    let splits = 1; // Initialize splits count
4    let currentGCD = 0; // Current greatest common divisor (GCD)
5
6    // Iterate through each number in the array
7    for (const num of nums) {
8        currentGCD = gcd(currentGCD, num); // Update the GCD
9
10        if (currentGCD == 1) {
11            // If GCD is 1, increment split count and reset the current GCD
12            splits++;
13            currentGCD = num;
14        }
15    }
16
17    // Return the total number of splits required
18    return splits;
19}
20
21// Calculate the greatest common divisor of two numbers 
22function gcd(a: number, b: number): number {
23    // If second number is zero, return the first number
24    if (b === 0) {
25        return a;
26    }
27
28    // Otherwise, continue the process recursively using Euclid's algorithm
29    return gcd(b, a % b);
30}
31
Not Sure What to Study? Take the 2-min Quiz

Which technique can we use to find the middle of a linked list?

Time and Space Complexity

The provided Python code defines a function minimumSplits that calculates the minimum number of non-empty groups to split the input list nums such that the greatest common divisor (GCD) of all numbers in the same group is not equal to 1.

Time Complexity:

The time complexity of the code is determined by the number of iterations in the for loop and the complexity of the gcd function calls within the loop.

  • The for loop runs once for each element in nums. If n is the number of elements in nums, the loop iterates n times.
  • For each iteration, the GCD of the current running GCD g and the current element x is calculated using the gcd function. The time complexity of the gcd function is generally O(log(min(a, b))) where a and b are the inputs to the gcd function. In the worst case, a and b could be the last two elements of nums.

Since the GCD decreases or stays the same with each iteration, the time complexity is better than O(n log m) with m being the maximum element in nums due to the iterations where g is reduced to 1, resetting the GCD calculation.

Overall, the worst-case time complexity of the minimumSplits function is O(n log m).

Space Complexity:

The space complexity is determined by the additional space used by the function.

  • The variables ans and g use constant space.
  • Since Python's gcd function has no additional space that depends on the input size (assuming it doesn't use a recursive stack that depends on the size of the values), it can be considered to use constant space.
  • No additional data structures are used that grow with the size of the input.

Thus, the space complexity is O(1) for constant extra space.

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

Fast Track Your Learning with Our Quick Skills Quiz:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«