2601. Prime Subtraction Operation

MediumGreedyArrayMathBinary SearchNumber Theory

Problem Description

You are provided with an array of integers, and the goal is to determine if you can transform this array into a strictly increasing array through a specific operation. The operation allows you to pick an index in the array that has not been picked before and then choose a prime number less than the value at that index. You subtract this prime number from the value at the chosen index. An array is considered strictly increasing if every element is larger than the element before it. You are allowed to perform this operation as many times as needed, as long as each index is only picked once. The main challenge is to find out whether it is possible to make the array strictly increasing through these operations and return true if it is possible, or false if it is not.

Intuition

The key insight to solving this problem is understanding that each non-increasing pair of elements in the array needs to be dealt with by subtracting a prime number in such a way as to make the current element less than the next. To accomplish this, we must consider the primes smaller than the current element.

Because we are ensuring strictly increasing order, we need to find primes that are just small enough to decrease the current number, but not so much that we can't maintain the strictly increasing property. We approach this by starting from the second-to-last element and moving backward, checking if the current number needs adjustment with respect to its subsequent number.

To optimize prime number finding and selection, we first pre-generate a list of all prime numbers smaller than the maximum number in the original array. We then use binary search to find the smallest prime number that we can subtract from the current number to make it smaller than the subsequent number.

The algorithm is designed to find the optimal prime for each element from back to front. If, at any point, we cannot find a suitable prime, we know it isn't possible to achieve a strictly increasing array, and we return false. If, after processing all elements, we haven't encountered this issue, we return true, as we've successfully transformed the array into a strictly increasing one.

Learn more about Greedy, Math and Binary Search patterns.

Solution Approach

The implementation of the solution uses two main algorithms: prime number generation and binary search, and it employs the list data structure to store the prime numbers and to manipulate the nums array.

Prime Number Generation

The prime number generation part of the algorithm involves creating a list of prime numbers up to the largest element in the nums array. We initialize an empty list p to store the prime numbers. We then iterate through numbers from 2 to the maximum number found in nums. For each number i, we test whether it is divisible by any previously identified prime numbers in the p list. If i is divisible by any of these primes, it is not prime and we skip to the next number. If no divisors are found, i is prime and we append it to the p list.

Binary Search for Prime Subtraction

Once we have our list of prime numbers, we then iterate through the nums array in reverse order, starting from the second-to-last element. For each element nums[i], we need to find a prime number p[j] that, when subtracted from nums[i], would make nums[i] less than nums[i+1]. This ensures the strictly increasing property for these two elements.

We use bisect_right from Python's bisect module to perform a binary search for the proper prime number that can be subtracted. bisect_right finds the index j in the prime list such that all the primes up to index j-1 are strictly less than nums[i] - nums[i+1]. If j is equal to the length of p or p[j] is greater than or equal to nums[i], it indicates there is no suitable prime that can be subtracted from nums[i] without making it negative or non-increasing with respect to nums[i+1]. In this case, we return false because it is impossible to make the array strictly increasing.

After the loop, if we have successfully found primes for all required elements, we return true, indicating it is possible to form a strictly increasing array with the specified operations.

To summarize, this approach cleverly combines efficient prime generation with binary search to minimize the number of elements that need to be checked and to quickly find the smallest appropriate prime for each subtraction operation. This results in an efficient algorithm suitable for processing arrays to determine if they can be made strictly increasing.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example. Consider the array nums = [10, 5, 15]. We want to determine if we can subtract prime numbers from each element (only once per element) to make the array strictly increasing.

First, we generate the list of prime numbers up to the largest number in nums, which is 15. So our list of primes p up to 15 would be [2, 3, 5, 7, 11, 13].

Following the solution approach:

We start from the second-to-last element in nums, which is 5 in this case.
We see that 5 is not less than 15 (the subsequent element), so we need to check if we can subtract a prime number from the element [10] to make it less than 5.
From the list p, we search for the smallest prime number that would make the element at index 0 smaller than 5 (the next element) when subtracted. Here, we can subtract 7 from 10 (10 - 7 = 3), and 3 is less than 5.
The array now looks like [3, 5, 15].
Upon iteratively checking all elements, we find that no more operations are needed because the array is already strictly increasing.
Since we were able to apply the operations to the array to make it strictly increasing, the final return value would be true.

To summarize the example, we navigated through each element of the array against its subsequent element, using binary search to quickly find a suitable prime to subtract from nums[i] to achieve the strictly increasing property. This process demonstrated the algorithm's strategy of prime subtraction and how it can effectively transform an array while adhering to the constraints of the problem.

Solution Implementation

1from bisect import bisect_right
2from typing import List
3
4class Solution:
5    def primeSubOperation(self, nums: List[int]) -> bool:
6        # Generate a list of prime numbers less than the maximum element in nums
7        primes = []
8        max_num = max(nums) + 1  # set limit for sieve as max element in nums + 1
9        for current in range(2, max_num):
10            # Check divisibility by all previously found primes
11            for prime in primes:
12                if current % prime == 0:
13                    # Not a prime, since divisible by a prime in the list
14                    break
15            else:  # Loop didn't break, so it's a prime number
16                # Append the prime number to the list of primes
17                primes.append(current)
18
19        # Get the length of the input list
20        num_length = len(nums)
21      
22        # Traverse the list from back to front to ensure nums is strictly increasing
23        for i in range(num_length - 2, -1, -1):
24            # If the current element is already less than the next element, continue
25            if nums[i] < nums[i + 1]:
26                continue
27          
28            # Find the right index to insert difference using bisect_right
29            difference = nums[i] - nums[i + 1]
30            j = bisect_right(primes, difference)
31          
32            # Check if we have a prime number less than the difference
33            # If not, we cannot make nums strictly increasing thus return False
34            if j == len(primes) or primes[j] >= nums[i]:
35                return False
36          
37            # Substract the nearest smaller prime from the current element to maintain the condition nums[i] < nums[i + 1]
38            nums[i] -= primes[j]
39
40        # If all checks are passed, return True indicating nums can be made strictly increasing
41        return True
42

1class Solution {
2  
3    // Main method to check if a prime subtraction operation can make the array strictly increasing.
4    public boolean primeSubOperation(int[] nums) {
5        // Generate a list of prime numbers up to 1000
6        List<Integer> primes = new ArrayList<>();
7        for (int num = 2; num <= 1000; ++num) {
8            boolean isPrime = true;
9            for (int prime : primes) {
10                if (num % prime == 0) {
11                    isPrime = false;
12                    break;
13                }
14            }
15            if (isPrime) {
16                primes.add(num);
17            }
18        }
19
20        int length = nums.length;
21      
22        // Iterate over the array from the end to start
23        for (int i = length - 2; i >= 0; --i) {
24          
25            // Continue if the current number is less than the next (array is already increasing here)
26            if (nums[i] < nums[i + 1]) {
27                continue;
28            }
29          
30            // Use binary search to find the smallest prime such that it's less than the difference
31            int index = binarySearch(primes, nums[i] - nums[i + 1]);
32          
33            // If the prime is not found or greater than or equal to the current number, return false
34            if (index == primes.size() || primes.get(index) >= nums[i]) {
35                return false;
36            }
37          
38            // Subtract the prime number found from the current array element
39            nums[i] -= primes.get(index);
40        }
41      
42        // If no issues found, return true
43        return true;
44    }
45
46    // Helper method to perform binary search and find the smallest prime number greater than x
47    private int binarySearch(List<Integer> primes, int x) {
48        int left = 0, right = primes.size();
49        while (left < right) {
50            int mid = (left + right) >> 1; // Equivalent to (left + right) / 2 but avoids overflow
51            if (primes.get(mid) > x) {
52                right = mid;
53            } else {
54                left = mid + 1;
55            }
56        }
57        // Return the index of the smallest prime number greater than x
58        return left;
59    }
60}
61

1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    bool primeSubOperation(vector<int>& nums) {
7        vector<int> primes;
8        // Generate all prime numbers up to 1000
9        for (int i = 2; i <= 1000; ++i) {
10            bool isPrime = true;
11            // Check if 'i' is divisible by any known prime
12            for (int prime : primes) {
13                if (i % prime == 0) {
14                    isPrime = false;
15                    break;
16                }
17            }
18            // If 'i' is prime, add it to the list of primes
19            if (isPrime) {
20                primes.push_back(i);
21            }
22        }
23      
24        int size = nums.size();
25        // Process each number in the array starting from the second-to-last
26        for (int i = size - 2; i >= 0; --i) {
27            // If the current element is smaller than the next one, move on
28            if (nums[i] < nums[i + 1]) {
29                continue;
30            }
31          
32            // Find the smallest prime such that nums[i] - prime is larger than nums[i + 1]
33            int idx = upper_bound(primes.begin(), primes.end(), nums[i] - nums[i + 1]) - primes.begin();
34          
35            // If no such prime exists or the prime is greater than or equal to nums[i], return false
36            if (idx == primes.size() || primes[idx] >= nums[i]) {
37                return false;
38            }
39          
40            // Reduce nums[i] by the found prime number to satisfy the condition
41            nums[i] -= primes[idx];
42        }
43      
44        // If all elements satisfy the condition, return true
45        return true;
46    }
47};
48

1// A function to determine whether a series of subtraction operations can make the array strictly increasing
2// by subtracting a prime number from an element if necessary.
3function primeSubOperation(nums: number[]): boolean {
4
5    // Store prime numbers in an array
6    const primes: number[] = [];
7  
8    // Generate prime numbers up to 1000 and store them in the primes array
9    for (let i = 2; i <= 1000; ++i) {
10        let isPrime = true;
11        for (const prime of primes) {
12            if (i % prime === 0) {
13                isPrime = false;
14                break;
15            }
16        }
17        if (isPrime) {
18            primes.push(i);
19        }
20    }
21
22    // Binary search to find the index of the smallest prime number 
23    // which is greater than the given number x
24    const searchPrimeIndex = (x: number): number => {
25        let left = 0;
26        let right = primes.length;
27        while (left < right) {
28            const mid = (left + right) >> 1;
29            if (primes[mid] > x) {
30                right = mid;
31            } else {
32                left = mid + 1;
33            }
34        }
35        return left;
36    };
37
38    // Iterate through the numbers array, starting from the second to last element, moving backwards
39    const count = nums.length;
40    for (let i = count - 2; i >= 0; --i) {
41        // Continue to the next if the current number is less than the next number (strictly increasing)
42        if (nums[i] < nums[i + 1]) {
43            continue;
44        }
45
46        // Find the index of the smallest prime number that is greater than the difference needed
47        const primeIndex = searchPrimeIndex(nums[i] - nums[i + 1]);
48
49        // If we cannot find a suitable prime number to make the sequence increasing, return false
50        if (primeIndex === primes.length || primes[primeIndex] >= nums[i]) {
51            return false;
52        }
53
54        // Perform the subtraction to make the sequence strictly increasing
55        nums[i] -= primes[primeIndex];
56    }
57
58    // If all values are checked and the array can be made strictly increasing, return true
59    return true;
60}
61

Time and Space Complexity

The time complexity of the given code can be analyzed in several parts:

Generating the prime numbers up to max(nums) involves checking each number against all previously found primes. In the worst case, if max(nums) is a prime number itself, this would generate O(max(nums) / \log(max(nums))) primes, since the density of primes is roughly 1 / \log(n) where n is the number being considered for primality. However, this check is done O(\sqrt{max(num)}) times for each number since we only need to check divisibility up to its square root. This gives us a complexity of O(max(nums) \sqrt{max(nums)} / \log(max(nums))) for the loop generating primes.
The main processing of nums array iterates over the elements once, which contributes O(n), where n is the length of nums.
The bisect_right function is used within the loop over nums. Assuming that the list of prime numbers is roughly m in size, where m is O(max(nums) / \log(max(nums))), the bisect_right operation contributes O(\log m) complexity each time it's called. It's called once for each of n iterations, so that part contributes O(n \log m).
The operation nums[i] -= p[j] is constant time, O(1).

Considering the time complexities together, the dominating term is from generating the primes and the iterative process with binary search. Since the prime generation complexity is less common in analysis, we'll assume that max(nums) is bounded by a polynomial size of n, which means that m is O(n / \log(n)). Hence, we focus on the O(n \log m) term for binary search within the loop. This suggests a time complexity of O(n(\log(n) - \log(\log(n)))), which simplifies to O(n \log n) under the assumption that max(nums) is not exponentially larger than n.

The space complexity of the algorithm is dominated by the list p that stores the primes. As calculated before, this will be about O(max(nums) / \log(max(nums))). Using the same bounding assumption as for the time complexity, we see that this simplifies to O(n), under the assumption that max(nums) is not exponentially larger than n.

So, in agreement with the reference answer, we can say the time complexity is O(n \log n) and the space complexity is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the following is a good use case for backtracking?

Combinatorial problems

Random number generation

Topological sorting

Matrix multiplication

I don’t know