Skip to content

2601. Prime Subtraction Operation

SourceWeekly Contest 338 Q2DifficultyMediumRating1779

Description

You are given a 0-indexed integer array nums of length n.

You can perform the following operation as many times as you want:

  • Pick an index i that you haven’t picked before, and pick a prime p strictly less than nums[i], then subtract p from nums[i].

Return true if you can make nums a strictly increasing array using the above operation and false otherwise.

A strictly increasing array is an array whose each element is strictly greater than its preceding element.

 

Example 1:

Input: nums = [4,9,6,10]
Output: true
Explanation: In the first operation: Pick i = 0 and p = 3, and then subtract 3 from nums[0], so that nums becomes [1,9,6,10].
In the second operation: i = 1, p = 7, subtract 7 from nums[1], so nums becomes equal to [1,2,6,10].
After the second operation, nums is sorted in strictly increasing order, so the answer is true.

Example 2:

Input: nums = [6,8,11,12]
Output: true
Explanation: Initially nums is sorted in strictly increasing order, so we don't need to make any operations.

Example 3:

Input: nums = [5,8,3]
Output: false
Explanation: It can be proven that there is no way to perform operations to make nums sorted in strictly increasing order, so the answer is false.

 

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000
  • nums.length == n

Solutions

Thinking

Each index may subtract a prime at most once, and the array must become strictly increasing. Greedy left-to-right may compress a value too far for later positions. Enumerating primes at every index is feasible for \(n \le 1000\) and values at most \(1000\), but the scan direction still matters.

The rightmost value \(nums[n-1]\) is freer when larger, so we process from right to left. When \(nums[i] \ge nums[i+1]\), we must subtract a prime strictly larger than \(nums[i]-nums[i+1]\) and smaller than \(nums[i]\), taking the smallest such prime so the left side keeps as much room as possible.

We therefore sieve primes up to \(1000\) into \(p\) and binary-search the least prime above that lower bound. If none exists, the array cannot be made strictly increasing.

We first preprocess all the primes within \(1000\) and record them in the array \(p\).

For each element \(nums[i]\) in the array \(nums\), we need to find a prime \(p[j]\) such that \(p[j] \gt nums[i] - nums[i + 1]\) and \(p[j]\) is as small as possible. If there is no such prime, it means that it cannot be strictly increased by subtraction operations, return false. If there is such a prime, we will subtract \(p[j]\) from \(nums[i]\) and continue to process the next element.

If all the elements in \(nums\) are processed, it means that it can be strictly increased by subtraction operations, return true.

The time complexity is \(O(n \log n)\) and the space complexity is \(O(n)\). where \(n\) is the length of the array \(nums\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def primeSubOperation(self, nums: List[int]) -> bool:
        p = []
        for i in range(2, max(nums)):
            for j in p:
                if i % j == 0:
                    break
            else:
                p.append(i)

        n = len(nums)
        for i in range(n - 2, -1, -1):
            if nums[i] < nums[i + 1]:
                continue
            j = bisect_right(p, nums[i] - nums[i + 1])
            if j == len(p) or p[j] >= nums[i]:
                return False
            nums[i] -= p[j]
        return True

 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 boolean primeSubOperation(int[] nums) {
        List<Integer> p = new ArrayList<>();
        for (int i = 2; i <= 1000; ++i) {
            boolean ok = true;
            for (int j : p) {
                if (i % j == 0) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                p.add(i);
            }
        }
        int n = nums.length;
        for (int i = n - 2; i >= 0; --i) {
            if (nums[i] < nums[i + 1]) {
                continue;
            }
            int j = search(p, nums[i] - nums[i + 1]);
            if (j == p.size() || p.get(j) >= nums[i]) {
                return false;
            }
            nums[i] -= p.get(j);
        }
        return true;
    }

    private int search(List<Integer> nums, int x) {
        int l = 0, r = nums.size();
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums.get(mid) > x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

 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
class Solution {
public:
    bool primeSubOperation(vector<int>& nums) {
        vector<int> p;
        for (int i = 2; i <= 1000; ++i) {
            bool ok = true;
            for (int j : p) {
                if (i % j == 0) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                p.push_back(i);
            }
        }
        int n = nums.size();
        for (int i = n - 2; i >= 0; --i) {
            if (nums[i] < nums[i + 1]) {
                continue;
            }
            int j = upper_bound(p.begin(), p.end(), nums[i] - nums[i + 1]) - p.begin();
            if (j == p.size() || p[j] >= nums[i]) {
                return false;
            }
            nums[i] -= p[j];
        }
        return true;
    }
};

 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
func primeSubOperation(nums []int) bool {
    p := []int{}
    for i := 2; i <= 1000; i++ {
        ok := true
        for _, j := range p {
            if i%j == 0 {
                ok = false
                break
            }
        }
        if ok {
            p = append(p, i)
        }
    }
    for i := len(nums) - 2; i >= 0; i-- {
        if nums[i] < nums[i+1] {
            continue
        }
        j := sort.SearchInts(p, nums[i]-nums[i+1]+1)
        if j == len(p) || p[j] >= nums[i] {
            return false
        }
        nums[i] -= p[j]
    }
    return true
}

 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
function primeSubOperation(nums: number[]): boolean {
    const p: number[] = [];
    for (let i = 2; i <= 1000; ++i) {
        let ok = true;
        for (const j of p) {
            if (i % j === 0) {
                ok = false;
                break;
            }
        }
        if (ok) {
            p.push(i);
        }
    }
    const search = (x: number): number => {
        let l = 0;
        let r = p.length;
        while (l < r) {
            const mid = (l + r) >> 1;
            if (p[mid] > x) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    };
    const n = nums.length;
    for (let i = n - 2; i >= 0; --i) {
        if (nums[i] < nums[i + 1]) {
            continue;
        }
        const j = search(nums[i] - nums[i + 1]);
        if (j === p.length || p[j] >= nums[i]) {
            return false;
        }
        nums[i] -= p[j];
    }
    return true;
}

Solution 2: Preprocessing prime numbers

Thinking

Solution 1 binary-searches the prime table each time. With values at most \(1000\), we can index directly: let \(p[x]\) be the least prime that is at least \(x\). The lower bound \(nums[i]-nums[i+1]\) then becomes a single array access, removing the search.

The rest is unchanged: still right-to-left, still subtracting that smallest prime.

 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
function primeSubOperation(nums: number[]): boolean {
    const p: number[] = [];
    const max = Math.max(...nums);

    for (let i = 2; i < max; i++) {
        let isPrime = true;

        for (const x of p) {
            if (i % x === 0) {
                isPrime = false;
                break;
            }
        }

        while (isPrime && p.length <= i) {
            p.push(i);
        }
    }

    for (let i = nums.length - 2; i >= 0; i--) {
        if (nums[i] < nums[i + 1]) continue;

        const [x, next] = [nums[i], nums[i + 1]];
        const prime = p[x - next + 1];

        if (!prime || prime >= x) return false;
        nums[i] -= prime;
    }

    return true;
}

 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
function primeSubOperation(nums) {
    const p = [];
    const max = Math.max(...nums);

    for (let i = 2; i < max; i++) {
        let isPrime = true;

        for (const x of p) {
            if (i % x === 0) {
                isPrime = false;
                break;
            }
        }

        while (isPrime && p.length <= i) {
            p.push(i);
        }
    }

    for (let i = nums.length - 2; i >= 0; i--) {
        if (nums[i] < nums[i + 1]) continue;

        const [x, next] = [nums[i], nums[i + 1]];
        const prime = p[x - next + 1];

        if (!prime || prime >= x) return false;
        nums[i] -= prime;
    }

    return true;
}

Comments