Problem Description

LeetCode Problem 2601

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.

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.

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 1000
• nums.length == n

Difficulty: Medium

Tags: array, math, binary search, greedy, number theory

Rating: 90.37%

Solution Strategy

The solution employs a greedy approach combined with prime number theory. Here’s how we break it down:

1. First, we need a way to identify prime numbers
2. For each element, we want to find the largest possible prime number we can subtract while maintaining the increasing property
3. We process the array from left to right, keeping track of the previous element to ensure the increasing property

Python Implementation

class Solution:
    def primeSubOperation(self, nums: List[int]) -> bool:
        def is_prime(n):
            for f in range(2, int(sqrt(n) + 1)):
                if n % f == 0:
                    return False
            return True
        
        # Create a lookup table for prime numbers up to max(nums)
        primes = [False, False]  # 0 and 1 are not prime
        for i in range(2, max(nums)):
            if is_prime(i):
                primes.append(True)
            else:
                primes.append(False)
        
        prev = 0  # Initialize previous number as 0
        for n in nums:
            # Calculate how much room we have to work with
            upper_bound = n - prev
            
            # Find the largest prime we can subtract
            largest_p = 0
            for i in range(upper_bound-1, 1, -1):
                if primes[i]:
                    largest_p = i
                    break
            
            # Check if we can maintain strictly increasing property
            if n - largest_p <= prev:
                return False
            
            # Update previous number for next iteration
            prev = n - largest_p
            
        return True

Example Walkthrough

Let’s walk through Example 1: nums = [4, 9, 6, 10]

1. First Element (4):

   • Previous value = 0
   • We can subtract any prime less than 4
   • Largest such prime is 3
   • After subtraction: 4 - 3 = 1
   • New array: [1, 9, 6, 10]

2. Second Element (9):

   • Previous value = 1
   • We need the result to be > 1
   • Largest usable prime is 7
   • After subtraction: 9 - 7 = 2
   • New array: [1, 2, 6, 10]

3. Third Element (6):

   • Previous value = 2
   • We need the result to be > 2
   • Largest usable prime is 3
   • After subtraction: 6 - 3 = 3
   • New array: [1, 2, 3, 10]

4. Fourth Element (10):

   • Previous value = 3
   • We need the result to be > 3
   • Largest usable prime is 5
   • After subtraction: 10 - 5 = 5
   • Final array: [1, 2, 3, 5]

The final array is strictly increasing, so we return true.

Time and Space Complexity

• Time Complexity: $O(n * m * \sqrt{m})$ where $n$ is the number of elements and $m$ is the maximum element value
  • We process each element in the array
  • For each element, we find the largest prime to subtract
  • The prime lookup table is $O(m)$
• Space Complexity: $O(m)$ for the prime number lookup table

Key Insights

1. The greedy approach works because:

   • For each position, we want to subtract the largest possible prime to give maximum flexibility to subsequent numbers
   • If we can’t make it work with the largest possible prime, no smaller prime will work either

2. The prime number lookup table is crucial for performance:

   • We precompute all primes up to max(nums)
   • This allows constant-time lookup during the main processing loop