You are given a 0-indexed integer array nums of length n.
You can perform the following operation as many times as you want:
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 <= 10001 <= nums[i] <= 1000nums.length == nclass Solution {
public boolean primeSubOperation(int[] nums) {
int n = nums.length;
boolean[] primes = sieveOfEratosthenes(nums);
// System.out.println(Arrays.toString(primes));
int currVal = 1;
for (int i = 0; i < nums.length; currVal++) {
int diff = nums[i] - currVal;
if (diff < 0)
return false;
if (primes[diff] || diff == 0) {
i++;
// System.out.println(Arrays.toString(nums));
}
return true;
}
private boolean[] sieveOfEratosthenes(int[] nums) {
int n = nums.length, ceil = 0;
for (int i : nums)
ceil = Math.max(ceil, i);
boolean primes[] = new boolean[ceil + 1];
Arrays.fill(primes, true);
primes[0] = false;
primes[1] = false;
for (int curr = 2; curr <= ceil; curr++)
if (primes[curr])
for (int multiple = curr * curr; multiple <= ceil; multiple += curr)
primes[multiple] = false;
return primes;
}
}