2601. Prime Subtraction Operation

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

Solution 1: Preprocessing prime numbers + binary search

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\).

Python3JavaC++GoTypeScript

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

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;
    }
}

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;
    }
};

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
}

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

TypeScriptJavaScript

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;
}

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;
}

2601. Prime Subtraction Operation

Description

Solutions

Solution 1: Preprocessing prime numbers + binary search

Solution 2: Preprocessing prime numbers

Comments