# Prime Subtraction Operation
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/prime-subtraction-operation)
Canonical: https://scaleengineer.com/dsa/problems/prime-subtraction-operation
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
---
## Problem
You are given a **0-indexed** integer array `nums` of length `n`.

You can perform the following operation as many times as you want:

* Pick an index `i` that you haven’t picked before, and pick a prime `p` **strictly less than** `nums[i]`, then subtract `p` from `nums[i]`.

Return _true if you can make `nums` a strictly increasing array using the above operation and false otherwise._

A **strictly increasing array** is an array whose each element is strictly greater than its preceding element.

**Example 1:**

**Input:** nums = [4,9,6,10]
**Output:** true
**Explanation:** In the first operation: Pick i = 0 and p = 3, and then subtract 3 from nums[0], so that nums becomes [1,9,6,10].
In the second operation: i = 1, p = 7, subtract 7 from nums[1], so nums becomes equal to [1,2,6,10].
After the second operation, nums is sorted in strictly increasing order, so the answer is true.

**Example 2:**

**Input:** nums = [6,8,11,12]
**Output:** true
**Explanation:** Initially nums is sorted in strictly increasing order, so we don't need to make any operations.

**Example 3:**

**Input:** nums = [5,8,3]
**Output:** false
**Explanation:** It can be proven that there is no way to perform operations to make nums sorted in strictly increasing order, so the answer is false.

**Constraints:**

* `1 <= nums.length <= 1000`
* `1 <= nums[i] <= 1000`
* `nums.length == n`

# Approaches
## Dynamic Programming with Memoization
This approach explores all possible valid modifications to the array using recursion and memoization to avoid recomputing results for the same subproblems. A subproblem is defined by the current index being considered and the value of the preceding element.
**Time:** O(N * M * pi(M)), where `N` is the length of `nums`, `M` is the maximum possible value in `nums` (1000), and `pi(M)` is the number of primes less than `M`. The state space is `N * M`, and for each state, we iterate through up to `pi(M)` primes. · **Space:** O(N * M + M) for the memoization table and the list of primes, where N is `nums.length` and M is the maximum possible value in `nums`.
**Pros:** Guaranteed to find the correct answer by exploring all valid possibilities.
**Cons:** High time complexity, which might lead to a 'Time Limit Exceeded' error on larger constraints.; High space complexity due to the 2D memoization table.
### Explanation
We define a recursive function, say `solve(index, prev_val)`, which returns `true` if the subarray from `index` to the end can be made strictly increasing, given the previous element's value is `prev_val`.

The base case for the recursion is when `index` reaches the end of the array (`n`), which means we have successfully built a valid sequence, so we return `true`.

In the recursive step for `solve(index, prev_val)`, we have two main choices for the current element `nums[index]`:
1.  **No Operation:** If `nums[index]` is already strictly greater than `prev_val`, we can choose to not modify it. We then check if a solution exists for the rest of the array by calling `solve(index + 1, nums[index])`.
2.  **Subtraction Operation:** We can iterate through all prime numbers `p` strictly less than `nums[index]`. For each prime, we calculate the new value `new_val = nums[index] - p`. If `new_val` is strictly greater than `prev_val`, we check if a solution exists for the rest of the array by calling `solve(index + 1, new_val)`.

If any of these recursive calls return `true`, it means a valid sequence can be formed, and we return `true`. If all possibilities are exhausted without finding a solution, we return `false`.

To optimize this recursive exploration, we use a 2D memoization table, `memo[index][prev_val]`, to store the results of subproblems. This avoids redundant calculations and significantly improves performance from exponential to polynomial time.

We would also need a list of primes up to 1000, which can be pre-computed using a sieve.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    private List<Integer> primes;
    private int[][] memo;
    private int[] nums;
    private int n;

    public boolean primeSubtraction(int[] nums) {
        this.nums = nums;
        this.n = nums.length;
        this.memo = new int[n][1001];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        
        sieve(1000);

        return solve(0, 0);
    }

    private boolean solve(int index, int prevVal) {
        if (index == n) {
            return true;
        }
        if (memo[index][prevVal] != -1) {
            return memo[index][prevVal] == 1;
        }

        // Option 1: No operation
        if (nums[index] > prevVal) {
            if (solve(index + 1, nums[index])) {
                memo[index][prevVal] = 1;
                return true;
            }
        }

        // Option 2: Subtract a prime
        for (int p : primes) {
            if (p >= nums[index]) {
                break;
            }
            int newVal = nums[index] - p;
            if (newVal > prevVal) {
                if (solve(index + 1, newVal)) {
                    memo[index][prevVal] = 1;
                    return true;
                }
            }
        }

        memo[index][prevVal] = 0;
        return false;
    }

    private void sieve(int maxVal) {
        primes = new ArrayList<>();
        boolean[] isPrime = new boolean[maxVal + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int p = 2; p * p <= maxVal; p++) {
            if (isPrime[p]) {
                for (int i = p * p; i <= maxVal; i += p) {
                    isPrime[i] = false;
                }
            }
        }
        for (int p = 2; p <= maxVal; p++) {
            if (isPrime[p]) {
                primes.add(p);
            }
        }
    }
}
```
### Algorithm
- Pre-compute all prime numbers up to 1000 using the Sieve of Eratosthenes.
- Initialize a 2D memoization array `memo[n+1][1001]` with a value indicating 'not computed'.
- Define a recursive function `solve(index, prev_val)`:
    - If `index == n`, return `true`.
    - If `memo[index][prev_val]` is already computed, return its value.
    - **Try not modifying `nums[index]`**:
        - If `nums[index] > prev_val` and `solve(index + 1, nums[index])` is `true`, store and return `true`.
    - **Try modifying `nums[index]`**:
        - Iterate through each prime `p < nums[index]`.
        - Let `new_val = nums[index] - p`.
        - If `new_val > prev_val` and `solve(index + 1, new_val)` is `true`, store and return `true`.
    - If no path returns `true`, store and return `false`.
- The final answer is the result of `solve(0, 0)`.

## Greedy Approach
A more efficient approach is to use a greedy strategy. When processing the array from left to right, we make a locally optimal choice at each step. The key insight is that to make it easiest for the subsequent elements to be larger, we should make the current element as small as possible, while still being greater than the previous element.
**Time:** O(N + M log log M), where `N` is the length of `nums` and `M` is the maximum value (1000). The pre-computation takes `O(M log log M)` for the sieve and `O(M)` for the helper array. The main loop runs in `O(N)` time. · **Space:** O(M) to store the prime information and the `largestPrimeSmallerThan` array, where M is the maximum possible value in `nums` (around 1000).
**Pros:** Very efficient in both time and space.; The greedy choice is simple and proven to be optimal for this problem.
**Cons:** The correctness of the greedy strategy is not immediately obvious without careful reasoning.
### Explanation
The core idea is to iterate through the `nums` array from left to right, maintaining the value of the 'previous' element in the modified, strictly increasing sequence. Let's call this `prev`. Initially, `prev` can be considered 0.

For each element `nums[i]`, we first check if it's possible to make it larger than `prev`. If `nums[i]` is already less than or equal to `prev`, it's impossible. This is because any subtraction will only make `nums[i]` smaller, so it can never become greater than `prev`. In this case, we can immediately return `false`.

If `nums[i] > prev`, we have a valid starting point. To be greedy, we want to modify `nums[i]` to be the smallest possible value that is still greater than `prev`. This is achieved by subtracting the largest possible prime `p` from `nums[i]` such that the result `nums[i] - p` is still greater than `prev`.

This condition `nums[i] - p > prev` is equivalent to `p < nums[i] - prev`. So, we need to find the largest prime `p` that is strictly less than the difference `nums[i] - prev`.

If such a prime exists, we subtract it from `nums[i]` to get the new value for the current position. If no such prime exists (e.g., if `nums[i] - prev` is 2 or less), we cannot make `nums[i]` any smaller, so we leave it as is.

We then update `prev` to this new, possibly modified value of `nums[i]` and proceed to the next element.

If we successfully process the entire array, it means a valid sequence can be formed, and we return `true`.

To efficiently find the 'largest prime less than k', we can pre-compute this information for all numbers up to the maximum possible value.

```java
import java.util.Arrays;

class Solution {
    public boolean primeSubtraction(int[] nums) {
        int maxVal = 1002; // Max possible value for num or diff + buffer
        boolean[] isPrime = new boolean[maxVal];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int p = 2; p * p < maxVal; p++) {
            if (isPrime[p]) {
                for (int i = p * p; i < maxVal; i += p) {
                    isPrime[i] = false;
                }
            }
        }

        int[] largestPrimeSmallerThan = new int[maxVal];
        // largestPrimeSmallerThan[k] stores the largest prime < k
        for (int i = 3; i < maxVal; i++) {
            if (isPrime[i - 1]) {
                largestPrimeSmallerThan[i] = i - 1;
            } else {
                largestPrimeSmallerThan[i] = largestPrimeSmallerThan[i - 1];
            }
        }

        int prev = 0;
        for (int num : nums) {
            if (num <= prev) {
                return false;
            }
            int diff = num - prev;
            int p = largestPrimeSmallerThan[diff];
            
            if (p > 0) {
                prev = num - p;
            } else {
                prev = num;
            }
        }
        return true;
    }
}
```
### Algorithm
- Pre-compute all primes up to 1001 using a Sieve.
- Create an auxiliary array, `largestPrimeSmallerThan`, of size 1002. `largestPrimeSmallerThan[k]` will store the largest prime strictly less than `k`. This can be filled in `O(M)` time after the sieve.
- Initialize a variable `prev = 0`.
- Iterate through `nums` from `i = 0` to `n-1`:
    - If `nums[i] <= prev`, return `false`.
    - Calculate the difference: `diff = nums[i] - prev`.
    - Find the largest prime `p` less than `diff` using the pre-computed array: `p = largestPrimeSmallerThan[diff]`.
    - If a valid prime `p > 0` is found, update the current element's value for the next iteration: `current_val = nums[i] - p`.
    - Otherwise, we cannot subtract any prime, so `current_val = nums[i]`.
    - Update `prev = current_val`.
- If the loop completes, return `true`.

# Solutions
### Java

```java
class Solution {
public
  boolean primeSubOperation(int[] nums) {
    List<Integer> p = new ArrayList<>();
    for (int i = 2; i <= 1000; ++i) {
      boolean ok = true;
      for (int j : p) {
        if (i % j == 0) {
          ok = false;
          break;
        }
      }
      if (ok) {
        p.add(i);
      }
    }
    int n = nums.length;
    for (int i = n - 2; i >= 0; --i) {
      if (nums[i] < nums[i + 1]) {
        continue;
      }
      int j = search(p, nums[i] - nums[i + 1]);
      if (j == p.size() || p.get(j) >= nums[i]) {
        return false;
      }
      nums[i] -= p.get(j);
    }
    return true;
  }
private
  int search(List<Integer> nums, int x) {
    int l = 0, r = nums.size();
    while (l < r) {
      int mid = (l + r) >> 1;
      if (nums.get(mid) > x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool primeSubOperation(vector<int> &nums) {
    vector<int> p;
    for (int i = 2; i <= 1000; ++i) {
      bool ok = true;
      for (int j : p) {
        if (i % j == 0) {
          ok = false;
          break;
        }
      }
      if (ok) {
        p.push_back(i);
      }
    }
    int n = nums.size();
    for (int i = n - 2; i >= 0; --i) {
      if (nums[i] < nums[i + 1]) {
        continue;
      }
      int j =
          upper_bound(p.begin(), p.end(), nums[i] - nums[i + 1]) - p.begin();
      if (j == p.size() || p[j] >= nums[i]) {
        return false;
      }
      nums[i] -= p[j];
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def primeSubOperation(self, nums: List[int]) -> bool: p = [] for i in range(2, max(nums)): for j in p: if i % j == 0: break else: p . append(i) n = len(nums) for i in range(n - 2, - 1, - 1): if nums[i] < nums[i + 1]: continue j = bisect_right(p, nums[i] - nums[i + 1]) if j == len(p) or p[j] >= nums[i]: return False nums[i] -= p[j] return True

```