2601

2601. Prime Subtraction Operation (Medium)

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

Companies: Google

Related Topics:
Array, Math, Binary Search, Greedy, Number Theory

Hints:

• Think about if we have many primes to subtract from nums[i]. Which prime is more optimal?
• The most optimal prime to subtract from nums[i] is the one that makes nums[i] the smallest as possible and greater than nums[i-1].

Solution 1.

// OJ: https://leetcode.com/problems/prime-subtraction-operation
// Author: github.com/lzl124631x
// Time: O(NP) where N is the length of `A` and `P` is the number of primes within 1000
// Space: O(P)
class Solution {
public:
    bool primeSubOperation(vector<int>& A) {
        bool prime[1001] = {[0 ... 1000] = true};
        vector<int> primes;
        for (int i = 2; i <= 1000; ++i) {
            if (!prime[i]) continue;
            primes.push_back(i);
            int j = i * i;
            for (; j <= 1000; j += i) prime[j] = false;
        }
        for (int i = 0; i < A.size(); ++i) {
            int prev = i == 0 ? -1 : A[i - 1], j = lower_bound(begin(primes), end(primes), A[i]) - begin(primes) - 1;
            while (j >= 0 && A[i] - primes[j] <= prev) --j;
            if (j >= 0) A[i] -= primes[j];
            if (A[i] <= prev) return false;
        }
        return true;
    }
};

Or use binary search to find the optimal prime number directly.

// OJ: https://leetcode.com/problems/prime-subtraction-operation
// Author: github.com/lzl124631x
// Time: O(NlogP)
// Space: O(P)
class Solution {
public:
    bool primeSubOperation(vector<int>& A) {
        bool prime[1001] = {[0 ... 1000] = true};
        vector<int> primes{0};
        for (int i = 2; i <= 1000; ++i) {
            if (!prime[i]) continue;
            primes.push_back(i);
            int j = i * i;
            for (; j <= 1000; j += i) prime[j] = false;
        }
        for (int i = 0; i < A.size(); ++i) {
            int prev = i == 0 ? -1 : A[i - 1], L = 0, R = primes.size() - 1;
            while (L <= R) {
                int M = (L + R) / 2;
                if (primes[M] < A[i] && A[i] - primes[M] > prev) L = M + 1;
                else R = M - 1;
            }
            if (R < 0) return false;
            A[i] -= primes[R];
        }
        return true;
    }
};