2584. Split the Array to Make Coprime Products LeetCode Solution
In this guide, you will get 2584. Split the Array to Make Coprime Products LeetCode Solution with the best time and space complexity. The solution to Split the Array to Make Coprime Products problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Split the Array to Make Coprime Products
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.
For example, if 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.
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.length
1 <= n <= 104
1 <= nums[i] <= 106
Complexity Analysis
Time Complexity: O(n\sqrt{n})
Space Complexity: O(n\sqrt{n})
2584. Split the Array to Make Coprime Products LeetCode Solution in C++
class Solution {
public:
int findValidSplit(vector<int>& nums) {
unordered_map<int, int> leftPrimeFactors;
unordered_map<int, int> rightPrimeFactors;
for (const int num : nums)
for (const int primeFactor : getPrimeFactors(num))
++rightPrimeFactors[primeFactor];
for (int i = 0; i < nums.size() - 1; ++i) {
for (const int primeFactor : getPrimeFactors(nums[i])) {
if (--rightPrimeFactors[primeFactor] == 0) {
// rightPrimeFactors[primeFactor] == 0, so no need to track
// leftPrimeFactors[primeFactor].
rightPrimeFactors.erase(primeFactor);
leftPrimeFactors.erase(primeFactor);
} else {
// Otherwise, need to track leftPrimeFactors[primeFactor].
++leftPrimeFactors[primeFactor];
}
}
if (leftPrimeFactors.empty())
return i;
}
return -1;
}
private:
// Gets the prime factors under sqrt(10^6).
vector<int> getPrimeFactors(int num) {
vector<int> primeFactors;
for (int divisor = 2; divisor <= min(1000, num); ++divisor)
if (num % divisor == 0) {
primeFactors.push_back(divisor);
while (num % divisor == 0)
num /= divisor;
}
// Handle the case that `num` contains a prime factor > 1000.
if (num > 1)
primeFactors.push_back(num);
return primeFactors;
}
}; /* code provided by PROGIEZ */
2584. Split the Array to Make Coprime Products LeetCode Solution in Java
class Solution {
public int findValidSplit(int[] nums) {
Map<Integer, Integer> leftPrimeFactors = new HashMap<>();
Map<Integer, Integer> rightPrimeFactors = new HashMap<>();
for (final int num : nums)
for (final int primeFactor : getPrimeFactors(num))
rightPrimeFactors.merge(primeFactor, 1, Integer::sum);
for (int i = 0; i < nums.length - 1; ++i) {
for (final int primeFactor : getPrimeFactors(nums[i])) {
rightPrimeFactors.merge(primeFactor, -1, Integer::sum);
if (rightPrimeFactors.get(primeFactor) == 0) {
// rightPrimeFactors[primeFactor] == 0, so no need to track
// leftPrimeFactors[primeFactor].
rightPrimeFactors.remove(primeFactor);
leftPrimeFactors.remove(primeFactor);
} else {
// Otherwise, need to track leftPrimeFactors[primeFactor].
leftPrimeFactors.merge(primeFactor, 1, Integer::sum);
}
}
if (leftPrimeFactors.isEmpty())
return i;
}
return -1;
}
// Gets the prime factors under sqrt(10^6).
private List<Integer> getPrimeFactors(int num) {
List<Integer> primeFactors = new ArrayList<>();
for (int divisor = 2; divisor <= Math.min(1000, num); ++divisor)
if (num % divisor == 0) {
primeFactors.add(divisor);
while (num % divisor == 0)
num /= divisor;
}
// Handle the case that `num` contains a prime factor > 1000.
if (num > 1)
primeFactors.add(num);
return primeFactors;
}
} // code provided by PROGIEZ
2584. Split the Array to Make Coprime Products LeetCode Solution in Python
class Solution:
def findValidSplit(self, nums: list[int]) -> int:
leftPrimeFactors = collections.Counter()
rightPrimeFactors = collections.Counter()
def getPrimeFactors(num: int) -> list[int]:
"""Gets the prime factors under sqrt(10^6)."""
primeFactors = []
for divisor in range(2, min(1000, num) + 1):
if num % divisor == 0:
primeFactors.append(divisor)
while num % divisor == 0:
num //= divisor
# Handle the case that `num` contains a prime factor > 1000.
if num > 1:
primeFactors.append(num)
return primeFactors
for num in nums:
for primeFactor in getPrimeFactors(num):
rightPrimeFactors[primeFactor] += 1
for i in range(len(nums) - 1):
for primeFactor in getPrimeFactors(nums[i]):
rightPrimeFactors[primeFactor] -= 1
if rightPrimeFactors[primeFactor] == 0:
# rightPrimeFactors[primeFactor] == 0, so no need to track
# leftPrimeFactors[primeFactor].
del rightPrimeFactors[primeFactor]
del leftPrimeFactors[primeFactor]
else:
# Otherwise, need to track leftPrimeFactors[primeFactor].
leftPrimeFactors[primeFactor] += 1
if not leftPrimeFactors:
return i
return -1 # code by PROGIEZ
