Prime Subtraction Operation

Medium
701.

Prime Subtraction Operation

Prime Subtraction Operation is a medium coding problem on arrays, math and greedy, asked in Amazon, Google and Adobe interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var primeSubOperation = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Prime Subtraction Operation — Solution in Python, Java & C++

Prime Subtraction Operation solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Prime Subtraction Operation is a medium coding problem on arrays, math and greedy, asked in Amazon, Google and Adobe interviews.

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

Hints for Prime Subtraction Operation

  1. Hint 1

    Sweep left to right making each element as small as possible while staying above its predecessor.

  2. Hint 2

    That means subtracting the largest prime p < nums[i] for which nums[i] - p still exceeds the previous value.

  3. Hint 3

    A sieve up to 1000 gives you the primes once, up front.

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

  1. Sieve the primes below 1000 once.
  2. Track prev, the value settled on for the previous index, starting at 0.
  3. For each element, scan the primes in increasing order and remember the largest p < nums[i] with nums[i] - p > prev.
  4. 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

Java

public static boolean primeSubOperation(int[] nums) {
    final int LIMIT = 1001;
    boolean[] composite = new boolean[LIMIT];
    List<Integer> primes = new ArrayList<>();
    for (int p = 2; p < LIMIT; p++) {
        if (!composite[p]) {
            primes.add(p);
            for (int m = p * p; m < LIMIT; m += p) composite[m] = true;
        }
    }
    int prev = 0;
    for (int x : nums) {
        int best = 0;
        for (int p : primes) {
            if (p >= x) break;
            if (x - p > prev) best = p;
        }
        int value = x - best;
        if (value <= prev) return false;
        prev = value;
    }
    return true;
}

C++

bool primeSubOperation(vector<int>& nums) {
    const int LIMIT = 1001;
    vector<bool> composite(LIMIT, false);
    vector<int> primes;
    for (int p = 2; p < LIMIT; p++) {
        if (!composite[p]) {
            primes.push_back(p);
            for (int m = p * p; m < LIMIT; m += p) composite[m] = true;
        }
    }
    int prev = 0;
    for (int x : nums) {
        int best = 0;
        for (int p : primes) {
            if (p >= x) break;
            if (x - p > prev) best = p;
        }
        int 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Greedy Algorithms