⚡Flashcard Drill➔
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

  1. Scan left to right, maintaining prev, the final value chosen for the previous element (start at 0).
  2. For the current value v we must pick a prime p with v - p > prev, i.e. p < v - prev; picking the largest such prime makes v - p as small as possible, leaving maximum room for later elements.
  3. If v <= prev the element cannot be fixed, since subtracting a positive prime only decreases v.
  4. Precompute primes up to max(nums) with a sieve, then binary search for the largest prime below v - prev; if none exists, keep v unchanged (which requires v > 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 - p large and squeezes the following elements; the largest prime minimises the current value.
  • Omitting the v <= prev early exit: a prime subtraction can only lower v, so this case is hopeless.
  • Using bisect_right: p must be strictly less than v - prev, so bisect_left(...) - 1 is 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.
🎯 Drill This Card Now➔

🧩 Related Math & Geometry Problems