Problem 2601 Prime Subtraction Operation
Table of Contents
Problem Statement
Link - Problem 2601
Question
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 primep
strictly less thannums[i]
, then subtractp
fromnums[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
Solution
class Solution {
public:
bool primeSubOperation(vector<int>& nums) {
int maxElement = *max_element(nums.begin(), nums.end());
vector<bool> primes(maxElement + 1, true);
primes[1] = false;
for (int i = 2; i <= sqrt(maxElement + 1); i++) {
if (primes[i] == true) {
for (int j = i * i; j <= maxElement; j += i) {
primes[j] = false;
}
}
}
int currValue = 1;
int i = 0;
while (i < nums.size()) {
int difference = nums[i] - currValue;
if (difference < 0) {
return false;
}
if (primes[difference] || difference == 0) {
i++;
currValue++;
}
else {
currValue++;
}
}
return true;
}
};
Complexity Analysis
| Algorithm | Time Complexity | Space Complexity |
| --------------------------------------------- | ---------------- | ---------------- |
| Sieve of Eratosthenes with supplementary loop | O(m + nlogm + n) | O(m) |
Explanation
Intial Thoughts
The problem statement wants us to check if we can make the given array strictly increasing by subtracting a prime number less than the current number from it. Initial thoughts are to iterate through the array and check for each number if subtracting a prime number from it can make it fit in the increasing sequence. We will need a way to generate all prime numbers less than a certain limit. We can use the Sieve of Eratosthenes algorithm to generate all primes. Another thought is to keep track of the current value we are expecting in the strictly increasing sequence.
Intuitive Analysis
Let’s iterate through the array and track the current value. If we can subtract a prime number less than the current number, we increment the current value and move to the next number in the array. But if subtracting any prime number does not make the current number greater than the previous number, we simply increment the current value. This will ensure that we are always expecting the next number in the strictly increasing sequence. We continue this process until we have checked all numbers in the array. If we reach the end without returning false, then it means we can make the array strictly increasing by the given operation.
1. Intuition
- The problem requires us to determine if we can make the given array strictly increasing by subtracting a prime number less than the current element.
- We can approach this problem by first finding all prime numbers less than the maximum element in the array.
- We then iterate through the array and for each element, we check if the difference between the current element and the previous element is a prime number.
- If the difference is a prime number, we can subtract it from the current element to make the array strictly increasing.
- If the difference is not a prime number, we cannot make the array strictly increasing and we return false.
- We continue this process until we have iterated through the entire array.
- If we are able to make the array strictly increasing, we return true.
2. Implementation
- We first find the maximum element in the array using
*max_element(nums.begin(), nums.end())
. - We then create a boolean array
primes
of sizemaxElement + 1
and initialize all elements to true. - We iterate through the array and mark the multiples of each prime number as false using
primes[j] = false
. - We then iterate through the array and for each element, we check if the difference between the current element and the previous element is a prime number using
primes[difference]
. - If the difference is a prime number, we increment the current value and move to the next element using
currValue++
andi++
. - If the difference is not a prime number, we only increment the current value using
currValue++
. - We continue this process until we have iterated through the entire array using
while (i < nums.size())
.
Complexity Analysis
Time Complexity:
- The time complexity is determined by the Sieve of Eratosthenes algorithm (
for (int i = 2; i <= sqrt(maxElement + 1); i++)
andfor (int j = i * i; j <= maxElement; j += i)
) which has a time complexity of O(n log(log n)) where n is the maximum element in the input array. However, after generating the primes, there is an additional loop (while (i < nums.size())
) which has a time complexity of O(m) where m is the size of the input array. Therefore, the total time complexity is O(m + n log(log n)). - The dominant operations are the generation of primes using the Sieve of Eratosthenes algorithm and the subsequent loop to check for prime differences.
- The logarithmic term arises from the
sqrt(maxElement + 1)
in the outer loop of the Sieve of Eratosthenes algorithm. However, since the size of the input array m is generally smaller than the maximum element n, we can simplify the time complexity to O(m + n _ log m + n) = O(m _ log m + n * log n)
Space Complexity:
- The space complexity is determined by the storage of the prime numbers in the boolean array (
vector<bool> primes(maxElement + 1, true);
). - The size of this array is proportional to the maximum element in the input array, hence the space complexity is O(m) where m is the maximum element.
- This space complexity is justified as the maximum amount of memory used to store the prime numbers is directly proportional to the maximum element in the input array.
Footnote
This question is rated as Medium difficulty.
Hints
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].