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

LeetCode 2436 Solution 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.

: :

LeetCode 2436 Solutions in Java, C++, Python

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);
    }
}

Interactive Code Editor for LeetCode 2436

Improve Your LeetCode 2436 Solution

Use the editor below to refine the provided solution for LeetCode 2436. Select a programming language and try the following:

Add import statements if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.

Loading editor...

Sign in with Google

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