Determine if an Array Can Be Made Strictly Increasing by Prime Subtraction

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.

Solution:

First, if the array is already strictly increasing, we directly return 'true'.

Otherwise, we need to determine if we can make the array strictly increasing by performing the operations.

We can scan the array from left to right. For each position 'i', we need to find a prime 'p' such that 'p < nums[i]' and for 'j < i', 'nums[j] + p <= nums[i]'.

If we can find such a 'p', then we can subtract 'p' from 'nums[i]' to make 'nums[i] > nums[i-1]'.

If for some position 'i' we cannot find such a 'p', then we return 'false'.

Time Complexity: O(n^2 log n)

Space Complexity: O(n)

C++ Code:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool isPrime(int num) {
    if (num <= 1) {
        return false;
    }
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

bool canMakeIncreasing(vector<int>& nums) {
    int n = nums.size();
    if (n <= 1) {
        return true;
    }
    for (int i = 1; i < n; i++) {
        if (nums[i] > nums[i - 1]) {
            continue;
        }
        bool foundPrime = false;
        for (int j = 2; j < nums[i]; j++) {
            if (isPrime(j) && nums[i - 1] + j <= nums[i]) {
                foundPrime = true;
                break;
            }
        }
        if (!foundPrime) {
            return false;
        }
    }
    return true;
}

int main() {
    vector<int> nums = {1, 5, 3, 7};
    if (canMakeIncreasing(nums)) {
        cout << "True" << endl;
    } else {
        cout << "False" << endl;
    }
    return 0;
}