You are given a 0-indexed integer array nums of length n.
You can perform the following operation as many times as you want:
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 <= 10001 <= nums[i] <= 1000nums.length == nThe idea is to ensure every element is greater than its previous one by subtracting a suitable prime. We iterate through each element and subtract the smallest possible prime until the condition is met.
For each element in the array, find if there's a prime that can be subtracted to make the current element greater than the previous one. Repeat this for all elements until the array becomes strictly increasing.
This C solution iterates over the array elements and whenever a non-increasing pair is detected, it attempts to subtract the smallest prime number from the current element to make it bigger than the previous one. After adjusting each element, the code checks again if the array is strictly increasing.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * log(n)), primarily dominated by the prime-checking function.
Space Complexity: O(1), since we are modifying the array in place and not using any additional data structures.
This approach involves using the Sieve of Eratosthenes to precompute primes up to the maximum value in the array. For each element, we maintain a list of unpicked primes smaller than the current number and dynamically reduce the current element with the largest viable prime, proceeding until a strictly increasing order is established.
We use this optimized list to attempt to produce a valid increasing order to minimize operation count and improve efficiency.
This C solution uses a sieve to precompute all primes less than a given maximum value. This approach allows us to quickly identify potential subtraction values to transform the array into one that is strictly increasing.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * sqrt(m)), but preprocessing the prime sieve to reduce runtime cost per loop.
Space Complexity: O(m), for storing the boolean list to evaluate primes.
| Approach | Complexity |
|---|---|
| Prime Subtraction Greedy Approach | Time Complexity: O(n * log(n)), primarily dominated by the prime-checking function. |
| Optimized Prime Sieve with Early Exit | Time Complexity: O(n * sqrt(m)), but preprocessing the prime sieve to reduce runtime cost per loop. |
Prime Subtraction Operation - Leetcode 2601 - Python • NeetCodeIO • 9,958 views views
Watch 9 more video solutions →Practice Prime Subtraction Operation with our built-in code editor and test cases.
Practice on FleetCode