LeetCode Biweekly Contest 190 š„ | 3 Problems Solved | Q1āQ3 | 4034, 4035, 4036
Maximum Valid Split Positions I - Video Solution
Watch 2 video solutions for Maximum Valid Split Positions I, a medium level problem. This walkthrough by EdgeCaseOffByOne has 321 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given an integer array nums.
You may remove at most one element from nums. Let arr be the array of remaining elements in their original order, and let m be its length.
A split position i of arr is valid if:
0 <= i < m - 1, andgcd(arr[0..i]) == gcd(arr[i + 1..m - 1]).
An array of length 1 has no valid split positions.
The score of arr is the number of valid split positions in it.
Return the maximum possible score of arr.
Here, gcd(a) denotes the greatest common divisor of all elements in the array a.
Example 1:
Input: nums = [10,30,15,10]
Output: 2
Explanation:
One optimal solution is to remove nums[2] = 15. Then arr = [10, 30, 10].
The split positions are:
Split Position i |
gcd(arr[0..i]) |
gcd(arr[i + 1..m - 1]) |
|---|---|---|
| 0 | 10 | 10 |
| 1 | 10 | 10 |
All split positions are valid. Thus, the answer is 2.
Example 2:
Input: nums = [2,10,14]
Output: 1
Explanation:
One optimal solution is to not remove any element. Then arr = [2, 10, 14].
The split positions are:
Split Position i |
gcd(arr[0..i]) |
gcd(arr[i + 1..m - 1]) |
|---|---|---|
| 0 | 2 | 2 |
| 1 | 2 | 14 |
Only the split position at index 0 is valid. Thus, the answer is 1.
Example 3:
Input: nums = [2,4]
Output: 0
Explanation:
The only remaining array that has a split position is arr = [2, 4].
The split positions are:
Split Position i |
gcd(arr[0..i]) |
gcd(arr[i + 1..m - 1]) |
|---|---|---|
| 0 | 2 | 4 |
There are no valid split positions. Thus, the answer is 0.
Constraints:
2 <= nums.length <= 10001 <= nums[i] <= 109āāāāāāā