Problem

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.

A strictly increasing array is an array whose each element is strictly greater than its preceding element.

Examples

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.

Solution

Method 1 - Using Sieve of Eratosthenes

Here is the approach

  1. Prime Number Generation: Generate a list of prime numbers using the Sieve of Eratosthenes, since you may need to find prime numbers less than any element in the array.
  2. Transformation Attempt: Iterate through the given array to try to transform it into a strictly increasing array.
  3. Validation: For each element in the array, if it’s not possible to make the array strictly increasing, return false.
  4. Conditions:
    • For each element nums[i], it must be strictly greater than the previous element nums[i-1] after any required operations.
    • Use the largest prime number less than nums[i] to achieve this if necessary.

Code

Java
class Solution {
    public boolean primeSubOperation(int[] nums) {
        int n = nums.length;
        List<Integer> primes = sievePrimes(Collections.max(Arrays.stream(nums).boxed().toList()));
        
        for (int i = 0; i < n; i++) {
            for (int j = primes.size() - 1; j >= 0; j--) {
                int p = primes.get(j);
                if (p < nums[i] && (i == 0 || nums[i] - p > nums[i - 1])) {
                    nums[i] -= p;
                    break;
                }
            }
            if (i > 0 && nums[i] <= nums[i - 1]) {
                return false;
            }
        }
        return true;
    }
    
    private List<Integer> sievePrimes(int max) {
        boolean[] isPrime = new boolean[max + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
        
        for (int i = 2; i * i <= max; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= max; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= max; i++) {
            if (isPrime[i]) {
                primes.add(i);
            }
        }
        
        return primes;
    }
}
Python
class Solution:
    def primeSubOperation(self, nums: List[int]) -> bool:
        def sieve_primes(max_num: int) -> List[int]:
            is_prime = [True] * (max_num + 1)
            is_prime[0] = is_prime[1] = False
            
            for i in range(2, int(max_num ** 0.5) + 1):
                if is_prime[i]:
                    for j in range(i * i, max_num + 1, i):
                        is_prime[j] = False
            
            return [i for i, prime in enumerate(is_prime) if prime]
        
        n = len(nums)
        primes = sieve_primes(max(nums))
        
        for i in range(n):
            for p in reversed(primes):
                if p < nums[i] and (i == 0 or nums[i] - p > nums[i - 1]):
                    nums[i] -= p
                    break
            if i > 0 and nums[i] <= nums[i - 1]:
                return False
        
        return True

Complexity

  • ⏰ Time complexity: O(m * log(log(m))) + O(n * (m / log(m)), where m is max in array
    • Prime generation using the Sieve of Eratosthenes: O(m * log(log(m)))
    • Array traversal and transformation: O(n * p)
      • n is the size of the array.
      • p is the number of prime numbers less than m, which is approximately m / log(m).
      • For each element in the array, we iterate through the list of primes in a worst-case scenario.
  • 🧺 Space complexity: O(m) for storing primes
    • We store a boolean array of size m+1 for primality checks.