Prime Subtraction Operation

Leetcode Problem:

• Prime Subtraction Operation

Summary

• Given a 0-indexed integer array, determine if it can be made a strictly increasing array by subtracting prime numbers from its elements.

Approach

• The approach involves first creating a boolean array to store the primality of numbers from 2 to 1000
• Then, for each number in the input array, we try to subtract the smallest prime that is less than the number from it
• If the resulting number is less than the previous number, we return false
• Otherwise, we continue with the next number
• If we can successfully make the array strictly increasing, we return true.

Complexity

• O(n * sqrt(1000))

Explanation

• The time complexity is O(n * sqrt(1000)) because for each number in the input array, we try to subtract the smallest prime that is less than the number from it
• The outer loop runs n times, and the inner loop runs up to sqrt(1000) times
• The space complexity is O(1000) because we need to store the primality of numbers from 2 to 1000 in the boolean array.

Solution Code:

class Solution {
public:
    bool isPrime[1001];
    bool primeSubOperation(vector& nums) {
        for(int i = 2 ; i <= 1000; i++){
            isPrime[i] = true;
        }
        for(int i = 2; i*i <= 1000; i++){
            for(int j = 2; i*j <= 1000; j++){
                isPrime[i*j] = false;
            }
        }
        for(int i = nums[0] - 1; i >= 2; i--){
            if(isPrime[i]){
                nums[0] -= i;
                break;
            }
        }
        for(int i = 1; i < nums.size(); i++){
            for(int j = nums[i] - 1; j >= 2; j--){
                if(isPrime[j] && nums[i-1] < (nums[i] - j)){
                    nums[i] -= j;
                    break;
                }
            }
            if(nums[i-1] >= nums[i]) return false;
        }

        return true;
    }
};