2601. Prime Subtraction Operation
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 EvaluatorExample 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, ifmax(nums)
is a prime number itself, this would generateO(max(nums) / \log(max(nums)))
primes, since the density of primes is roughly1 / \log(n)
wheren
is the number being considered for primality. However, this check is doneO(\sqrt{max(num)})
times for each number since we only need to check divisibility up to its square root. This gives us a complexity ofO(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 contributesO(n)
, wheren
is the length ofnums
. -
The
bisect_right
function is used within the loop overnums
. Assuming that the list of prime numbers is roughlym
in size, wherem
isO(max(nums) / \log(max(nums)))
, thebisect_right
operation contributesO(\log m)
complexity each time it's called. It's called once for each ofn
iterations, so that part contributesO(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.
What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at