2601. Prime Subtraction Operation

Problem

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

Solution (Java)

class Solution {
    public boolean primeSubOperation(int[] nums) {
        List<Integer> primes = sieveOfEratosthenes(1000);
        for (int i = nums.length; i >= 2; i--) {
            if (nums[i - 2] >= nums[i - 1]) {
                int index = -1;
                for (int primeIndex = 0; primeIndex < primes.size(); primeIndex++) {
                    if (primes.get(primeIndex) >= nums[i - 2]) {
                        break;
                    }

                    if (nums[i - 2] - primes.get(primeIndex) < nums[i - 1]) {
                        index = primeIndex;
                        break;
                    }
                }
                if (index == -1) {
                    return false;
                }
                nums[i - 2] = nums[i - 2] - primes.get(index);
            }
        }
        return true;
    }
    public List<Integer> sieveOfEratosthenes(int count) {
        List<Integer> result = new ArrayList<>();
        boolean[] primes = new boolean[count + 1];
        for (int i = 0; i < primes.length; i++) {
            primes[i] = true;
        }
        for (int i = 2; i * i <= count; i++) {
            if (primes[i]) {
                for (int j = i * 2; j <= count; j = j + i) {
                    primes[j] = false;
                }
            }
        }
        for (int i = 2; i <= count; i++) {
            if (primes[i]) {
                result.add(i);
            }
        }
        return result;
    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).