2716. Prime Subtraction Operation¶

LeetCode Problem View on GitHub

2716. 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

Solution¶

class Solution {
    private int isprime[];
    public boolean primeSubOperation(int[] nums) {
        isprime = new int[1001];
        sieve();
        int n = nums.length;
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] >= nums[i + 1]) {
                for (int j = 2; j < nums[i]; j++) {
                    if (isprime[j] == 1) {
                        if (nums[i] - j < nums[i + 1]) {
                            nums[i] -= j;
                            break;
                        }
                    }
                }
            }
        }
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] >= nums[i + 1]) return false;
        }
        return true;
    }

    private void sieve() {
        Arrays.fill(isprime, 1);
        isprime[0] = isprime[1] = 0;
        for (int i = 2; i <= 1000; i++) {
            if (isprime[i] == 1) {
                for (int j = i; j * i < 1000 + 1; j++) {
                    if (isprime[j * i] == 1) {
                        isprime[j * i] = 0;
                    }
                }
            }
        }
    }
}

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here