Check if an Array Can Be Made Strictly Increasing After Prime Subtraction

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

Here's the C++ code using depth-first search (DFS) to solve this problem:

class Solution {
public:
    bool isIncreasing(vector<int>& nums) {
        int n = nums.size();
        for (int i = 1; i < n; i++) {
            if (nums[i] <= nums[i - 1]) {
                return false;
            }
        }
        return true;
    }
    
    bool dfs(vector<int>& nums, int i, vector<bool>& used) {
        if (i == nums.size()) {
            return isIncreasing(nums);
        }
        for (int p = 2; p < nums[i]; p++) {
            if (!used[p]) {
                used[p] = true;
                int tmp = nums[i];
                nums[i] -= p;
                if (dfs(nums, i + 1, used)) {
                    return true;
                }
                nums[i] = tmp;
                used[p] = false;
            }
        }
        return dfs(nums, i + 1, used);
    }
    
    bool canMakeIncreasing(vector<int>& nums) {
        int n = nums.size();
        vector<bool> used(10001, false); // prime numbers <= 10000
        return dfs(nums, 0, used);
    }
};

Explanation:

The 'dfs' function explores all possible combinations of prime subtraction operations using recursion. It iterates through each index 'i' of the array 'nums' and considers all prime numbers 'p' less than 'nums[i]'. For each prime 'p', it subtracts 'p' from 'nums[i]' and recursively calls 'dfs' for the next index. If the recursive call returns 'true', indicating that the array can be made strictly increasing, then the function returns 'true'. Otherwise, it restores the original value of 'nums[i]' and continues exploring other prime numbers.

The 'isIncreasing' function checks if an array is strictly increasing, which is used as the base case for the recursion. The 'canMakeIncreasing' function initializes a boolean array 'used' to keep track of which prime numbers have been used for subtraction and calls the 'dfs' function to start the exploration process.

Time Complexity: O(2^n * n), where 2^n represents the number of possible combinations of operations, and 'n' is the number of iterations for prime number enumeration.

Space Complexity: O(10001 + n), where 10001 is the size of the prime number array, and 'n' is the space used for the recursion stack.