Skip to content

4035. Maximum Valid Split Positions I

Description

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, and
  • gcd(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 <= 1000
  • 1 <= nums[i] <= 109​​​​​​​

Solutions

Solution 1: Enumerate the Removed Index + Prefix and Suffix GCD

Thinking

Split \(i\) is valid if and only if the prefix GCD on the left equals the suffix GCD on the right. For \(n\le 1000\) we need not analyse how a deletion perturbs the GCD chain.

Enumerate the deleted index (and the case of deleting nothing), build prefix and suffix GCDs of the remaining array, count equal splits, and keep the maximum.

One scoring pass is \(O(n\log M)\), so the total \(O(n^2\log M)\) time is acceptable.

Since the array length satisfies \(n \leq 1000\), we can enumerate the index of the removed element (including the case where nothing is removed) to obtain the array \(\textit{arr}\), compute the score of \(\textit{arr}\), and take the maximum over all cases.

For an array \(\textit{arr}\) of length \(m\), we precompute the prefix GCD array \(\textit{pre}\) and the suffix GCD array \(\textit{suf}\), where \(\textit{pre}[i] = \gcd(\textit{arr}[0..i])\) and \(\textit{suf}[i] = \gcd(\textit{arr}[i..m - 1])\). A split position \(i\) is valid if and only if \(\textit{pre}[i] = \textit{suf}[i + 1]\), so the score of \(\textit{arr}\) is the number of indices satisfying this condition.

The time complexity is \(O(n^2 \times \log M)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the array \(\textit{nums}\), and \(M\) is the maximum value in the array \(\textit{nums}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def maxValidSplits(self, nums: List[int]) -> int:
        def calc(arr: List[int]) -> int:
            m = len(arr)
            pre = list(accumulate(arr, gcd))
            suf = list(accumulate(arr[::-1], gcd))[::-1]
            return sum(pre[i] == suf[i + 1] for i in range(m - 1))

        ans = calc(nums)
        for i in range(len(nums)):
            ans = max(ans, calc(nums[:i] + nums[i + 1 :]))
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    public int maxValidSplits(int[] nums) {
        int n = nums.length;
        int ans = 0;
        for (int del = -1; del < n; ++del) {
            int m = del == -1 ? n : n - 1;
            int[] arr = new int[m];
            for (int i = 0, j = 0; i < n; ++i) {
                if (i != del) {
                    arr[j++] = nums[i];
                }
            }
            ans = Math.max(ans, calc(arr));
        }
        return ans;
    }

    private int calc(int[] arr) {
        int m = arr.length;
        int[] pre = new int[m];
        int[] suf = new int[m];
        pre[0] = arr[0];
        for (int i = 1; i < m; ++i) {
            pre[i] = gcd(pre[i - 1], arr[i]);
        }
        suf[m - 1] = arr[m - 1];
        for (int i = m - 2; i >= 0; --i) {
            suf[i] = gcd(suf[i + 1], arr[i]);
        }
        int ans = 0;
        for (int i = 0; i < m - 1; ++i) {
            if (pre[i] == suf[i + 1]) {
                ++ans;
            }
        }
        return ans;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    int maxValidSplits(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        for (int del = -1; del < n; ++del) {
            vector<int> arr;
            arr.reserve(n);
            for (int i = 0; i < n; ++i) {
                if (i != del) {
                    arr.push_back(nums[i]);
                }
            }
            ans = max(ans, calc(arr));
        }
        return ans;
    }

private:
    int calc(const vector<int>& arr) {
        int m = arr.size();
        vector<int> pre(m), suf(m);
        pre[0] = arr[0];
        for (int i = 1; i < m; ++i) {
            pre[i] = gcd(pre[i - 1], arr[i]);
        }
        suf[m - 1] = arr[m - 1];
        for (int i = m - 2; i >= 0; --i) {
            suf[i] = gcd(suf[i + 1], arr[i]);
        }
        int ans = 0;
        for (int i = 0; i < m - 1; ++i) {
            if (pre[i] == suf[i + 1]) {
                ++ans;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
func maxValidSplits(nums []int) int {
    n := len(nums)
    calc := func(arr []int) int {
        m := len(arr)
        pre := make([]int, m)
        suf := make([]int, m)
        pre[0] = arr[0]
        for i := 1; i < m; i++ {
            pre[i] = gcd(pre[i-1], arr[i])
        }
        suf[m-1] = arr[m-1]
        for i := m - 2; i >= 0; i-- {
            suf[i] = gcd(suf[i+1], arr[i])
        }
        ans := 0
        for i := 0; i < m-1; i++ {
            if pre[i] == suf[i+1] {
                ans++
            }
        }
        return ans
    }
    ans := 0
    for del := -1; del < n; del++ {
        arr := make([]int, 0, n)
        for i, x := range nums {
            if i != del {
                arr = append(arr, x)
            }
        }
        ans = max(ans, calc(arr))
    }
    return ans
}

func gcd(a, b int) int {
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
function maxValidSplits(nums: number[]): number {
    const n = nums.length;
    const gcd = (a: number, b: number): number => (b === 0 ? a : gcd(b, a % b));
    const calc = (arr: number[]): number => {
        const m = arr.length;
        const pre: number[] = Array(m).fill(0);
        const suf: number[] = Array(m).fill(0);
        pre[0] = arr[0];
        for (let i = 1; i < m; ++i) {
            pre[i] = gcd(pre[i - 1], arr[i]);
        }
        suf[m - 1] = arr[m - 1];
        for (let i = m - 2; i >= 0; --i) {
            suf[i] = gcd(suf[i + 1], arr[i]);
        }
        let ans = 0;
        for (let i = 0; i < m - 1; ++i) {
            if (pre[i] === suf[i + 1]) {
                ++ans;
            }
        }
        return ans;
    };
    let ans = 0;
    for (let del = -1; del < n; ++del) {
        const arr: number[] = [];
        for (let i = 0; i < n; ++i) {
            if (i !== del) {
                arr.push(nums[i]);
            }
        }
        ans = Math.max(ans, calc(arr));
    }
    return ans;
}

Comments