LeetCode 2436: Minimum Split Into Subarrays With GCD Greater Than One Solution

Master LeetCode problem 2436 (Minimum Split Into Subarrays With GCD Greater Than One), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2436. Minimum Split Into Subarrays With GCD Greater Than One

Medium

Array Math Dynamic Programming Greedy Number Theory

Problem Explanation

Explanation:

To solve this problem, we can use dynamic programming. We will iterate through each element in the array and keep track of the maximum subarray length with a GCD greater than one ending at that index. We can maintain a map where the key is the GCD value and the value is the length of the subarray with that GCD ending at the current index.

At each index, we will calculate the GCD of the current element with all previous GCD values in the map. If the GCD is greater than one, we update the map with the new subarray length ending at the current index.

Finally, we return the maximum value in the map, which represents the maximum subarray length with a GCD greater than one.

Time Complexity:

The time complexity of this approach is O(n * sqrt(max(arr))) where n is the number of elements in the array and max(arr) is the maximum element in the array.

Space Complexity:

The space complexity is O(sqrt(max(arr))) for the map.

: :

Solution Code

class Solution {
    public int splitArray(int[] nums) {
        Map<Integer, Integer> dp = new HashMap<>();
        int maxLen = 1;
        
        for (int num : nums) {
            Map<Integer, Integer> newDp = new HashMap<>();
            newDp.put(num, Math.max(newDp.getOrDefault(num, 0), 1));
            
            for (int key : dp.keySet()) {
                int newGcd = gcd(key, num);
                if (newGcd > 1) {
                    newDp.put(newGcd, Math.max(newDp.getOrDefault(newGcd, 0), dp.get(key) + 1));
                }
            }
            
            dp = newDp;
            maxLen = Math.max(maxLen, Collections.max(dp.values()));
        }
        
        return maxLen;
    }
    
    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2436 (Minimum Split Into Subarrays With GCD Greater Than One)?

This page provides optimized solutions for LeetCode problem 2436 (Minimum Split Into Subarrays With GCD Greater Than One) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2436 (Minimum Split Into Subarrays With GCD Greater Than One)?

The time complexity for LeetCode 2436 (Minimum Split Into Subarrays With GCD Greater Than One) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2436 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2436 in Java, C++, or Python.

Back to LeetCode Solutions