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 == nIn #2601 Prime Subtraction Operation, the goal is to determine whether an array can become strictly increasing by subtracting a prime number from each element at most once. The key insight is to process the array from left to right while ensuring every element remains greater than the previous value.
A common strategy is to precompute prime numbers using a sieve (such as the Sieve of Eratosthenes). For each element nums[i], we attempt to subtract the largest possible prime that still keeps the value greater than the previous element. This greedy decision maximizes flexibility for later elements.
To efficiently locate the best prime candidate, store all primes in a sorted list and use binary search to find the largest prime smaller than the allowed difference. If no valid prime keeps the sequence strictly increasing, the operation fails.
This approach combines greedy selection, prime preprocessing, and binary search, giving efficient performance for typical constraints.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sieve + Greedy with Binary Search | O(M log log M + N log P) | O(M) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Think about if we have many primes to subtract from nums[i]. Which prime is more optimal?
The most optimal prime to subtract from nums[i] is the one that makes nums[i] the smallest as possible and greater than nums[i-1].
The 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.
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.
1import java.util.*;
2
3public class PrimeSubtraction {
4 private static boolean isPrime(int num) {
5
In Java, this solution adheres to the same logical approach - checking the condition and modifying elements with the smallest prime necessary to meet the requirements for a strictly increasing order.
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.
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems like Prime Subtraction Operation appear in coding interviews because they combine number theory, greedy logic, and binary search. While the exact question may vary, similar patterns are commonly tested in technical interviews.
The optimal approach uses a greedy strategy combined with prime preprocessing. By generating primes using the Sieve of Eratosthenes and using binary search to find the best prime to subtract, we ensure each element stays just above the previous value.
A greedy strategy works because subtracting the largest valid prime keeps the current number as small as possible while still maintaining a strictly increasing order. This leaves more room for future elements to remain valid.
A list or array of precomputed prime numbers is essential. Keeping the primes sorted allows binary search to quickly find the best candidate prime for subtraction during each step.
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.