2601. Prime Subtraction Operation
Description
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
ithat you haven’t picked before, and pick a primepstrictly less thannums[i], then subtractpfromnums[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 <= 10001 <= nums[i] <= 1000nums.length == n
Solutions
Solution 1: Preprocessing prime numbers + binary search
We first preprocess all the primes within $1000$ and record them in the array $p$.
For each element $nums[i]$ in the array $nums$, we need to find a prime $p[j]$ such that $p[j] \gt nums[i] - nums[i + 1]$ and $p[j]$ is as small as possible. If there is no such prime, it means that it cannot be strictly increased by subtraction operations, return false. If there is such a prime, we will subtract $p[j]$ from $nums[i]$ and continue to process the next element.
If all the elements in $nums$ are processed, it means that it can be strictly increased by subtraction operations, return true.
The time complexity is $O(n \log n)$ and the space complexity is $O(n)$. where $n$ is the length of the array $nums$.
Python3
class Solution:
def primeSubOperation(self, nums: List[int]) -> bool:
p = []
for i in range(2, max(nums)):
for j in p:
if i % j == 0:
break
else:
p.append(i)
n = len(nums)
for i in range(n - 2, -1, -1):
if nums[i] < nums[i + 1]:
continue
j = bisect_right(p, nums[i] - nums[i + 1])
if j == len(p) or p[j] >= nums[i]:
return False
nums[i] -= p[j]
return True
Java
class Solution {
public boolean primeSubOperation(int[] nums) {
List<Integer> p = new ArrayList<>();
for (int i = 2; i <= 1000; ++i) {
boolean ok = true;
for (int j : p) {
if (i % j == 0) {
ok = false;
break;
}
}
if (ok) {
p.add(i);
}
}
int n = nums.length;
for (int i = n - 2; i >= 0; --i) {
if (nums[i] < nums[i + 1]) {
continue;
}
int j = search(p, nums[i] - nums[i + 1]);
if (j == p.size() || p.get(j) >= nums[i]) {
return false;
}
nums[i] -= p.get(j);
}
return true;
}
private int search(List<Integer> nums, int x) {
int l = 0, r = nums.size();
while (l < r) {
int mid = (l + r) >> 1;
if (nums.get(mid) > x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
}
C++
class Solution {
public:
bool primeSubOperation(vector<int>& nums) {
vector<int> p;
for (int i = 2; i <= 1000; ++i) {
bool ok = true;
for (int j : p) {
if (i % j == 0) {
ok = false;
break;
}
}
if (ok) {
p.push_back(i);
}
}
int n = nums.size();
for (int i = n - 2; i >= 0; --i) {
if (nums[i] < nums[i + 1]) {
continue;
}
int j = upper_bound(p.begin(), p.end(), nums[i] - nums[i + 1]) - p.begin();
if (j == p.size() || p[j] >= nums[i]) {
return false;
}
nums[i] -= p[j];
}
return true;
}
};
Go
func primeSubOperation(nums []int) bool {
p := []int{}
for i := 2; i <= 1000; i++ {
ok := true
for _, j := range p {
if i%j == 0 {
ok = false
break
}
}
if ok {
p = append(p, i)
}
}
for i := len(nums) - 2; i >= 0; i-- {
if nums[i] < nums[i+1] {
continue
}
j := sort.SearchInts(p, nums[i]-nums[i+1]+1)
if j == len(p) || p[j] >= nums[i] {
return false
}
nums[i] -= p[j]
}
return true
}
TypeScript
function primeSubOperation(nums: number[]): boolean {
const p: number[] = [];
for (let i = 2; i <= 1000; ++i) {
let ok = true;
for (const j of p) {
if (i % j === 0) {
ok = false;
break;
}
}
if (ok) {
p.push(i);
}
}
const search = (x: number): number => {
let l = 0;
let r = p.length;
while (l < r) {
const mid = (l + r) >> 1;
if (p[mid] > x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
const n = nums.length;
for (let i = n - 2; i >= 0; --i) {
if (nums[i] < nums[i + 1]) {
continue;
}
const j = search(nums[i] - nums[i + 1]);
if (j === p.length || p[j] >= nums[i]) {
return false;
}
nums[i] -= p[j];
}
return true;
}
Solution 2: Preprocessing prime numbers
TypeScript
function primeSubOperation(nums: number[]): boolean {
const p: number[] = [];
const max = Math.max(...nums);
for (let i = 2; i < max; i++) {
let isPrime = true;
for (const x of p) {
if (i % x === 0) {
isPrime = false;
break;
}
}
while (isPrime && p.length <= i) {
p.push(i);
}
}
for (let i = nums.length - 2; i >= 0; i--) {
if (nums[i] < nums[i + 1]) continue;
const [x, next] = [nums[i], nums[i + 1]];
const prime = p[x - next + 1];
if (!prime || prime >= x) return false;
nums[i] -= prime;
}
return true;
}
JavaScript
function primeSubOperation(nums) {
const p = [];
const max = Math.max(...nums);
for (let i = 2; i < max; i++) {
let isPrime = true;
for (const x of p) {
if (i % x === 0) {
isPrime = false;
break;
}
}
while (isPrime && p.length <= i) {
p.push(i);
}
}
for (let i = nums.length - 2; i >= 0; i--) {
if (nums[i] < nums[i + 1]) continue;
const [x, next] = [nums[i], nums[i + 1]];
const prime = p[x - next + 1];
if (!prime || prime >= x) return false;
nums[i] -= prime;
}
return true;
}