Intuition

The problem requires checking if we can make a strictly increasing sequence by subtracting prime numbers from array elements. The key insight is to work backwards through the array, ensuring each element becomes less than the next by subtracting the smallest possible prime number that achieves this condition.

Approach

1. Prime Number Precomputation:
2. Use Sieve of Eratosthenes to precompute all prime numbers up to 1000

3. Store primes in a list for quick access during binary search

4. Array Processing:

5. Start from second-to-last element (index n-2)

6. For each element nums[i], if it's >= nums[i+1]:

   • Calculate minimum prime needed: target = nums[i] - nums[i+1] + 1
   • Find smallest prime ≥ target using binary search
   • If no suitable prime exists or prime ≥ current number, return false
   • Subtract found prime from current number

7. Binary Search Optimization:

8. Use binary search to efficiently find the first prime number ≥ target
9. This ensures we use the smallest possible prime number for each subtraction

Complexity

• Time complexity: O(n log p)
• n is array length
• p is number of primes ≤ 1000
• Sieve initialization is O(m log log m) where m = 1000, but done once

• Each element requires at most one binary search: O(log p)

• Space complexity: O(1)

• Fixed size boolean array (1001) for Sieve
• Fixed size list for storing primes up to 1000
• Space doesn't depend on input array size

Code

class Solution {
    private static final boolean[] isPrime = new boolean[1001];
    private static final List<Integer> primes = new ArrayList<>();

    static {
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        for (int i = 2; i * i <= 1000; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= 1000; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        for (int i = 2; i <= 1000; i++) {
            if (isPrime[i]) {
                primes.add(i);
            }
        }
    }

    public boolean primeSubOperation(int[] nums) {
        int n = nums.length;

        if (n == 1) {
            return true;
        }

        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] >= nums[i + 1]) {
                int target = nums[i] - nums[i + 1] + 1;
                int primeToSubtract = findFirstLargerPrime(target, nums[i]);

                if (primeToSubtract == -1 || primeToSubtract >= nums[i]) {
                    return false;
                }
                nums[i] -= primeToSubtract;
            }
        }

        return true;
    }

    private int findFirstLargerPrime(int target, int maxVal) {
        int left = 0, right = primes.size() - 1;
        int result = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int prime = primes.get(mid);

            if (prime >= target) {
                result = prime;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return result < maxVal ? result : -1;
    }
}