> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Prime Subtraction Operation Python Solution

> Tested Python solution for LeetCode 2601 with 26 pytest cases. Generate a practice environment with lcpy.

LeetCode 2601, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Math](/catalog/topics/math), [Binary Search](/catalog/topics/binary-search), [Greedy](/catalog/topics/greedy), [Number Theory](/catalog/topics/number-theory). [View on LeetCode](https://leetcode.com/problems/prime-subtraction-operation/description/).

Generate this problem as a practice environment: tested reference solution, 26 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 2601   # by problem number
lcpy gen -s prime_subtraction_operation   # by problem name
```

## 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.

### Examples

```
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.
```

```
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.
```

```
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`

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/prime_subtraction_operation/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/prime_subtraction_operation/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from bisect import bisect_left


class Solution:
    # Time: O(n log P + P log log P) where P = max(nums)
    # Space: O(P)
    def prime_sub_operation(self, nums: list[int]) -> bool:
        limit = max(nums)
        sieve = [True] * (limit + 1)
        if limit >= 0:
            sieve[0] = False
        if limit >= 1:
            sieve[1] = False
        for i in range(2, int(limit**0.5) + 1):
            if sieve[i]:
                for multiple in range(i * i, limit + 1, i):
                    sieve[multiple] = False
        primes = [i for i in range(2, limit + 1) if sieve[i]]

        prev = 0
        for num in nums:
            # Largest prime p < num - prev keeps the resulting value as small as
            # possible while still exceeding prev; a smaller value is never worse.
            idx = bisect_left(primes, num - prev) - 1
            value = num - primes[idx] if idx >= 0 else num
            if value <= prev:
                return False
            prev = value
        return True
```

## Complexity

| Time | Space |
| - | - |
| O(n log P + P log log P) where P = max(nums) | O(P) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.