NeetCode #934LC-2601MediumMath & Geometry
← Back to All Problems#934 · #2601 · Prime Subtraction Operation(质数减法运算)
📌 Problem Statement & Constraints
Given an array
nums, you may perform any number of operations: pick an unused index i and a prime p, then replace nums[i] with nums[i] - p (the result must stay positive). Each index is used at most once. Return whether nums can be made strictly increasing. Constraints: 1 <= nums.length <= 1000, 1 <= nums[i] <= 1000.💡 Core Algorithmic Approaches
- Scan left to right, maintaining
prev, the final value chosen for the previous element (start at 0). - For the current value
vwe must pick a primepwithv - p > prev, i.e.p < v - prev; picking the largest such prime makesv - pas small as possible, leaving maximum room for later elements. - If
v <= prevthe element cannot be fixed, since subtracting a positive prime only decreasesv. - Precompute primes up to
max(nums)with a sieve, then binary search for the largest prime belowv - prev; if none exists, keepvunchanged (which requiresv > prev).
💻 Benchmark Python3 Implementation
class Solution:
def primeSubOperation(self, nums: List[int]) -> bool:
from bisect import bisect_left
mx = max(nums)
is_prime = [True] * (mx + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(mx ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, mx + 1, i):
is_prime[j] = False
primes = [i for i in range(2, mx + 1) if is_prime[i]]
prev = 0
for v in nums:
if v <= prev:
return False
# largest prime p with p < v - prev, so that v - p stays above prev
idx = bisect_left(primes, v - prev) - 1
prev = v - primes[idx] if idx >= 0 else v
return True⚡ Complexity Deep Dive
⏱️ Time Complexity
O(V log log V + n log V) with V = max(nums): the sieve plus one binary search per element.
💾 Space Complexity
O(V): the sieve table and prime list.
⚠️ Interview Pitfalls & Follow-ups
- Choosing the smallest feasible prime: that leaves
v - plarge and squeezes the following elements; the largest prime minimises the current value. - Omitting the
v <= prevearly exit: a prime subtraction can only lowerv, so this case is hopeless. - Using
bisect_right:pmust be strictly less thanv - prev, sobisect_left(...) - 1is correct. - Re-testing primality for each element: precomputing the sieve is essential to stay within the time limit.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.