Skip to content

4037. Maximum Valid Split Positions II

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 <= 105
  • 1 <= nums[i] <= 109​​​​​​​

Solutions

Solution 1: Prefix and Suffix GCD + Enumerate Candidate Removed Indices

Thinking

Scoring every deletion in \(O(n)\) no longer works for \(n=10^5\). Each prefix GCD divides the previous one, so the chain changes at most \(O(\log M)\) times.

If neither the prefix nor the suffix GCD changes at an index, deleting it leaves every other GCD untouched and only merges two split positions, so the score cannot increase. Only indices where a GCD actually changes are worth recomputing.

One forward mark and one backward mark produce \(O(\log M)\) candidates; we rescore each deletion and take the maximum with the score of the intact array.

Following the idea of the previous problem, for an array \(\textit{arr}\) of length \(m\) we precompute the prefix GCD array \(\textit{pre}\) and the suffix GCD array \(\textit{suf}\). 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. However, \(n\) can be as large as \(10^5\) here, so enumerating every removed index and spending \(O(n)\) on each of them is too slow.

Observe that every entry of the prefix GCD sequence divides the previous one, so it is at least halved whenever it changes, meaning the whole sequence changes only \(O(\log M)\) times. If the prefix GCD does not change at index \(i\), i.e. \(\textit{pre}[i] = \textit{pre}[i - 1]\), which is equivalent to \(\textit{pre}[i - 1]\) dividing \(\textit{nums}[i]\), then removing \(\textit{nums}[i]\) leaves every prefix GCD unchanged. Likewise, if the suffix GCD does not change at index \(i\) either, removing it leaves every suffix GCD unchanged as well. In that case the only effect of the removal is to merge the split positions \(i - 1\) and \(i\) into a single one, and those two positions are either both valid or both invalid, so the score can only decrease.

Therefore only the indices where the prefix GCD changes or the suffix GCD changes are worth enumerating, and there are at most \(O(\log M)\) of them. We call \(\textit{mark}\) once forward and once backward to collect the candidate indices, then compute the score with \(\textit{calc}\) after removing each candidate, and take the maximum together with the score of the untouched array.

The time complexity is \(O(n \times \log^2 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
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
43
44
45
46
47
class Solution:
    def maxValidSplits(self, nums: List[int]) -> int:
        n = len(nums)

        def calc(arr):
            m = len(arr)
            pre = [0] * m
            suf = [0] * m

            pre[0] = arr[0]
            for i in range(1, m):
                pre[i] = gcd(pre[i - 1], arr[i])

            suf[-1] = arr[-1]
            for i in range(m - 2, -1, -1):
                suf[i] = gcd(suf[i + 1], arr[i])

            ans = 0
            for i in range(m - 1):
                if pre[i] == suf[i + 1]:
                    ans += 1

            return ans

        def mark(arr):
            pos = [False] * n
            pos[0] = True
            g = arr[0]

            for i in range(1, n):
                ng = gcd(g, arr[i])
                pos[i] = ng != g
                g = ng

            return pos

        pos1 = mark(nums)
        pos2 = mark(nums[::-1])

        ans = calc(nums)

        for i in range(n):
            if pos1[i] or pos2[n - 1 - i]:
                arr = nums[:i] + nums[i + 1 :]
                ans = max(ans, calc(arr))

        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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class Solution {
    public int maxValidSplits(int[] nums) {
        int n = nums.length;

        boolean[] pos1 = mark(nums);

        int[] rev = nums.clone();
        for (int i = 0; i < n / 2; ++i) {
            int t = rev[i];
            rev[i] = rev[n - 1 - i];
            rev[n - 1 - i] = t;
        }

        boolean[] pos2 = mark(rev);

        int ans = calc(nums);

        for (int i = 0; i < n; ++i) {
            if (pos1[i] || pos2[n - 1 - i]) {
                int[] arr = new int[n - 1];
                for (int j = 0, k = 0; j < n; ++j) {
                    if (j != i) {
                        arr[k++] = nums[j];
                    }
                }
                ans = Math.max(ans, calc(arr));
            }
        }

        return ans;
    }

    private boolean[] mark(int[] nums) {
        int n = nums.length;
        boolean[] pos = new boolean[n];

        pos[0] = true;
        int g = nums[0];

        for (int i = 1; i < n; ++i) {
            int ng = gcd(g, nums[i]);
            pos[i] = ng != g;
            g = ng;
        }

        return pos;
    }

    private int calc(int[] arr) {
        int n = arr.length;
        int[] pre = new int[n];
        int[] suf = new int[n];

        pre[0] = arr[0];
        for (int i = 1; i < n; ++i) {
            pre[i] = gcd(pre[i - 1], arr[i]);
        }

        suf[n - 1] = arr[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            suf[i] = gcd(suf[i + 1], arr[i]);
        }

        int ans = 0;
        for (int i = 0; i + 1 < n; ++i) {
            if (pre[i] == suf[i + 1]) {
                ++ans;
            }
        }

        return ans;
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int t = a % b;
            a = b;
            b = t;
        }
        return a;
    }
}

 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class Solution {
public:
    int maxValidSplits(vector<int>& nums) {
        int n = nums.size();

        vector<bool> pos1 = mark(nums);

        vector<int> rev = nums;
        reverse(rev.begin(), rev.end());
        vector<bool> pos2 = mark(rev);

        int ans = calc(nums);

        for (int i = 0; i < n; ++i) {
            if (pos1[i] || pos2[n - 1 - i]) {
                vector<int> arr;
                arr.reserve(n - 1);

                for (int j = 0; j < n; ++j) {
                    if (i != j) {
                        arr.push_back(nums[j]);
                    }
                }

                ans = max(ans, calc(arr));
            }
        }

        return ans;
    }

private:
    vector<bool> mark(const vector<int>& nums) {
        int n = nums.size();
        vector<bool> pos(n);

        pos[0] = true;
        int g = nums[0];

        for (int i = 1; i < n; ++i) {
            int ng = gcd(g, nums[i]);
            pos[i] = ng != g;
            g = ng;
        }

        return pos;
    }

    int calc(const vector<int>& arr) {
        int n = arr.size();
        vector<int> pre(n), suf(n);

        pre[0] = arr[0];
        for (int i = 1; i < n; ++i) {
            pre[i] = gcd(pre[i - 1], arr[i]);
        }

        suf[n - 1] = arr[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            suf[i] = gcd(suf[i + 1], arr[i]);
        }

        int ans = 0;
        for (int i = 0; i + 1 < n; ++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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
func maxValidSplits(nums []int) int {
    n := len(nums)

    pos1 := mark(nums)

    rev := make([]int, n)
    for i := 0; i < n; i++ {
        rev[i] = nums[n-1-i]
    }
    pos2 := mark(rev)

    ans := calc(nums)

    for i := 0; i < n; i++ {
        if pos1[i] || pos2[n-1-i] {
            arr := make([]int, 0, n-1)
            for j := 0; j < n; j++ {
                if i != j {
                    arr = append(arr, nums[j])
                }
            }
            ans = max(ans, calc(arr))
        }
    }

    return ans
}

func mark(nums []int) []bool {
    n := len(nums)
    pos := make([]bool, n)

    pos[0] = true
    g := nums[0]

    for i := 1; i < n; i++ {
        ng := gcd(g, nums[i])
        pos[i] = ng != g
        g = ng
    }

    return pos
}

func calc(arr []int) int {
    n := len(arr)
    pre := make([]int, n)
    suf := make([]int, n)

    pre[0] = arr[0]
    for i := 1; i < n; i++ {
        pre[i] = gcd(pre[i-1], arr[i])
    }

    suf[n-1] = arr[n-1]
    for i := n - 2; i >= 0; i-- {
        suf[i] = gcd(suf[i+1], arr[i])
    }

    ans := 0
    for i := 0; i+1 < n; i++ {
        if pre[i] == suf[i+1] {
            ans++
        }
    }

    return ans
}

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

 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
function maxValidSplits(nums: number[]): number {
    const n = nums.length;

    const pos1 = mark(nums);

    const rev = [...nums].reverse();
    const pos2 = mark(rev);

    let ans = calc(nums);

    for (let i = 0; i < n; ++i) {
        if (pos1[i] || pos2[n - 1 - i]) {
            const arr = nums.slice(0, i).concat(nums.slice(i + 1));
            ans = Math.max(ans, calc(arr));
        }
    }

    return ans;
}

function mark(nums: number[]): boolean[] {
    const n = nums.length;
    const pos = Array(n).fill(false);

    pos[0] = true;
    let g = nums[0];

    for (let i = 1; i < n; ++i) {
        const ng = gcd(g, nums[i]);
        pos[i] = ng !== g;
        g = ng;
    }

    return pos;
}

function calc(arr: number[]): number {
    const n = arr.length;
    const pre = Array(n);
    const suf = Array(n);

    pre[0] = arr[0];
    for (let i = 1; i < n; ++i) {
        pre[i] = gcd(pre[i - 1], arr[i]);
    }

    suf[n - 1] = arr[n - 1];
    for (let i = n - 2; i >= 0; --i) {
        suf[i] = gcd(suf[i + 1], arr[i]);
    }

    let ans = 0;
    for (let i = 0; i + 1 < n; ++i) {
        if (pre[i] === suf[i + 1]) {
            ++ans;
        }
    }

    return ans;
}

function gcd(a: number, b: number): number {
    while (b !== 0) {
        [a, b] = [b, a % b];
    }
    return a;
}

Comments