LeetCode 2584. Split the Array to Make Coprime Products Solution in Java, C++, Python & Go | Explanation + Code

Description

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.

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.length
• 1 <= n <= 104
• 1 <= nums[i] <= 106

Solutions

Solution 1

PythonJavaC++Go

class Solution: def findValidSplit(self, nums: List[int]) -> int: first = {} n = len(nums) last = list(range(n)) for i, x in enumerate(nums): j = 2 while j <= x // j: if x % j == 0: if j in first: last[first[j]] = i else: first[j] = i while x % j == 0: x //= j j += 1 if x > 1: if x in first: last[first[x]] = i else: first[x] = i mx = last[0] for i, x in enumerate(last): if mx < i: return mx mx = max(mx, x) return -1(code-box)

class Solution { public int findValidSplit(int[] nums) { Map<Integer, Integer> first = new HashMap<>(); int n = nums.length; int[] last = new int[n]; for (int i = 0; i < n; ++i) { last[i] = i; } for (int i = 0; i < n; ++i) { int x = nums[i]; for (int j = 2; j <= x / j; ++j) { if (x % j == 0) { if (first.containsKey(j)) { last[first.get(j)] = i; } else { first.put(j, i); } while (x % j == 0) { x /= j; } } } if (x > 1) { if (first.containsKey(x)) { last[first.get(x)] = i; } else { first.put(x, i); } } } int mx = last[0]; for (int i = 0; i < n; ++i) { if (mx < i) { return mx; } mx = Math.max(mx, last[i]); } return -1; } }(code-box)

class Solution { public: int findValidSplit(vector<int>& nums) { unordered_map<int, int> first; int n = nums.size(); vector<int> last(n); iota(last.begin(), last.end(), 0); for (int i = 0; i < n; ++i) { int x = nums[i]; for (int j = 2; j <= x / j; ++j) { if (x % j == 0) { if (first.count(j)) { last[first[j]] = i; } else { first[j] = i; } while (x % j == 0) { x /= j; } } } if (x > 1) { if (first.count(x)) { last[first[x]] = i; } else { first[x] = i; } } } int mx = last[0]; for (int i = 0; i < n; ++i) { if (mx < i) { return mx; } mx = max(mx, last[i]); } return -1; } };(code-box)

func findValidSplit(nums []int) int { first := map[int]int{} n := len(nums) last := make([]int, n) for i := range last { last[i] = i } for i, x := range nums { for j := 2; j <= x/j; j++ { if x%j == 0 { if k, ok := first[j]; ok { last[k] = i } else { first[j] = i } for x%j == 0 { x /= j } } } if x > 1 { if k, ok := first[x]; ok { last[k] = i } else { first[x] = i } } } mx := last[0] for i, x := range last { if mx < i { return mx } mx = max(mx, x) } return -1 }(code-box)