Prime Subtraction Operation — Medium Problem & Solution

You may pick any index i at most once and subtract from nums[i] any prime strictly smaller than nums[i].

Difficulty: Medium
Topics: Arrays, Math, Greedy, Number Theory
Asked at: Amazon, Google, Adobe
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You may pick any index i at most once and subtract from nums[i] any prime strictly smaller than nums[i].

Return true if these operations can make nums strictly increasing.

Example 1

Input: nums = [4,9,6,10]
Output: true
Explanation: Subtract 3 from 4 to get 1, subtract 7 from 9 to get 2, and leave 6 and 10.

Example 2

Input: nums = [6,8,11,12]
Output: true
Explanation: The array is already strictly increasing.

Example 3

Input: nums = [5,8,3]
Output: false
Explanation: 3 can only shrink, and it is already below 8.

Constraints

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

How to solve Prime Subtraction Operation

Greedy left to right: minimising each element leaves the most room for everything after it. For the current element, that means subtracting the largest legal prime that keeps it above its predecessor.

Approach

Sieve the primes below 1000 once.
Track prev, the value settled on for the previous index, starting at 0.
For each element, scan the primes in increasing order and remember the largest p < nums[i] with nums[i] - p > prev.
Apply it; if the result is still not greater than prev, return false. Otherwise set prev to it.

Why it works

Exchange argument: suppose a valid assignment leaves some element larger than the greedy choice. Replacing it with the greedy (smaller) value keeps it above its predecessor by construction and can only relax the constraint on the next element, so the greedy prefix extends to a full solution whenever one exists.

Complexity

Time — O(n · π(1000))
Space — O(1000)

Pitfalls

Subtracting the largest prime below nums[i] unconditionally can push the value below prev and wrongly report failure.
The prime must be strictly smaller than nums[i], so the result is always at least 1.
Each index may be operated on at most once, which is why the greedy considers a single subtraction per element.

Reference solution

Python

from typing import List

def primeSubOperation(nums: List[int]) -> bool:
    LIMIT = 1001
    composite = [False] * LIMIT
    primes = []
    for p in range(2, LIMIT):
        if not composite[p]:
            primes.append(p)
            for m in range(p * p, LIMIT, p):
                composite[m] = True
    prev = 0
    for x in nums:
        best = 0
        for p in primes:
            if p >= x:
                break
            if x - p > prev:
                best = p
        value = x - best
        if value <= prev:
            return False
        prev = value
    return True

JavaScript

var primeSubOperation = function(nums) {
    var LIMIT = 1001;
    var composite = [];
    for (var t = 0; t < LIMIT; t++) composite.push(false);
    var primes = [];
    for (var p = 2; p < LIMIT; p++) {
        if (!composite[p]) {
            primes.push(p);
            for (var m = p * p; m < LIMIT; m += p) composite[m] = true;
        }
    }
    var prev = 0;
    for (var i = 0; i < nums.length; i++) {
        var best = 0;
        for (var j = 0; j < primes.length; j++) {
            if (primes[j] >= nums[i]) break;
            if (nums[i] - primes[j] > prev) best = primes[j];
        }
        var value = nums[i] - best;
        if (value <= prev) return false;
        prev = value;
    }
    return true;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue