2601 - Prime Subtraction Operation

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

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;
      }
  };

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;
      }
  }

PYTHON

• from bisect import bisect_right
  
  class Solution:
      def primeSubOperation(self, nums):
          primes = []
          for i in range(2, 1001):
              is_prime = True
              for p in primes:
                  if i % p == 0:
                      is_prime = False
                      break
              if is_prime:
                  primes.append(i)
  
          n = len(nums)
          for i in range(n - 2, -1, -1):
              if nums[i] < nums[i + 1]:
                  continue
              j = bisect_right(primes, nums[i] - nums[i + 1]) - 1
              if j == -1 or primes[j] >= nums[i]:
                  return False
              nums[i] -= primes[j]
  
          return True