The Indian Engineer

Problem 2601 Prime Subtraction Operation

Posted on 6 mins

Array Math Binary-Search Greedy Number Theory

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:

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:

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

2. Implementation


Complexity Analysis

Time Complexity:

Space Complexity:


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