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

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.

: :

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