You are given a 0-indexed integer array nums of length n.
A split at an index i where 0 <= i <= n - 2 is called valid if the product of the first i + 1 elements and the product of the remaining elements are coprime.
nums = [2, 3, 3], then a split at the index i = 0 is valid because 2 and 9 are coprime, while a split at the index i = 1 is not valid because 6 and 3 are not coprime. A split at the index i = 2 is not valid because i == n - 1.Return the smallest index i at which the array can be split validly or -1 if there is no such split.
Two values val1 and val2 are coprime if gcd(val1, val2) == 1 where gcd(val1, val2) is the greatest common divisor of val1 and val2.
Example 1:
Input: nums = [4,7,8,15,3,5] Output: 2 Explanation: The table above shows the values of the product of the first i + 1 elements, the remaining elements, and their gcd at each index i. The only valid split is at index 2.
Example 2:
Input: nums = [4,7,15,8,3,5] Output: -1 Explanation: The table above shows the values of the product of the first i + 1 elements, the remaining elements, and their gcd at each index i. There is no valid split.
Constraints:
n == nums.length1 <= n <= 1041 <= nums[i] <= 106This approach involves calculating the prefix product up to each index, as well as the suffix product from each index to the end of the array. By iterating over possible splits, calculate the gcd of the prefix and suffix products to determine if they are coprime.
The function first calculates prefix and suffix products for the given array. It iterates through to find a valid split where the gcd of the prefix and suffix products is 1 (meaning they are coprime). The gcd function uses the Euclidean algorithm.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the array. Space Complexity: O(n) due to the storage for prefix and suffix products.
This approach seeks to optimize space usage by maintaining cumulative products during a single traversal of the array. Instead of using full prefix and suffix arrays, it updates running products directly and checks coprimeness on-the-fly.
The optimized C solution combines the prefix and suffix product calculation into a single pass, multiplying and dividing by elements of the array as appropriate, to check gcd for coprimeness directly.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), Space Complexity: O(1) since no additional arrays are used.
| Approach | Complexity |
|---|---|
| Prefix and Suffix Product Approach | Time Complexity: O(n), where n is the length of the array. Space Complexity: O(n) due to the storage for prefix and suffix products. |
| Cumulative Product with Single Pass | Time Complexity: O(n), Space Complexity: O(1) since no additional arrays are used. |
Product of Array Except Self - Leetcode 238 - Python • NeetCode • 747,485 views views
Watch 9 more video solutions →Practice Split the Array to Make Coprime Products with our built-in code editor and test cases.
Practice on FleetCode