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.
- 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 <= 10001 <= nums[i] <= 1000
Hints for Prime Subtraction Operation
Hint 1
Sweep left to right making each element as small as possible while staying above its predecessor.
Hint 2
That means subtracting the largest prime
p < nums[i]for whichnums[i] - pstill exceeds the previous value.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
- Sieve the primes below 1000 once.
- Track
prev, the value settled on for the previous index, starting at0. - For each element, scan the primes in increasing order and remember the largest
p < nums[i]withnums[i] - p > prev. - Apply it; if the result is still not greater than
prev, returnfalse. Otherwise setprevto 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 belowprevand 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 TrueJava
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