Scale Engineer

Prime Subtraction Operation

Med
#2381Time: O(N + M log log M), where `N` is the length of `nums` and `M` is the maximum value (1000). The pre-computation takes `O(M log log M)` for the sieve and `O(M)` for the helper array. The main loop runs in `O(N)` time.Space: O(M) to store the prime information and the `largestPrimeSmallerThan` array, where M is the maximum possible value in `nums` (around 1000).
Patterns
MathGreedyNumber Theory
Algorithms
Binary Search
Data structures
Array

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

A more efficient approach is to use a greedy strategy. When processing the array from left to right, we make a locally optimal choice at each step. The key insight is that to make it easiest for the subsequent elements to be larger, we should make the current element as small as possible, while still being greater than the previous element.

Algorithm

  • Pre-compute all primes up to 1001 using a Sieve.
  • Create an auxiliary array, largestPrimeSmallerThan, of size 1002. largestPrimeSmallerThan[k] will store the largest prime strictly less than k. This can be filled in O(M) time after the sieve.
  • Initialize a variable prev = 0.
  • Iterate through nums from i = 0 to n-1:
    • If nums[i] <= prev, return false.
    • Calculate the difference: diff = nums[i] - prev.
    • Find the largest prime p less than diff using the pre-computed array: p = largestPrimeSmallerThan[diff].
    • If a valid prime p > 0 is found, update the current element's value for the next iteration: current_val = nums[i] - p.
    • Otherwise, we cannot subtract any prime, so current_val = nums[i].
    • Update prev = current_val.
  • If the loop completes, return true.

Walkthrough

The core idea is to iterate through the nums array from left to right, maintaining the value of the 'previous' element in the modified, strictly increasing sequence. Let's call this prev. Initially, prev can be considered 0.

For each element nums[i], we first check if it's possible to make it larger than prev. If nums[i] is already less than or equal to prev, it's impossible. This is because any subtraction will only make nums[i] smaller, so it can never become greater than prev. In this case, we can immediately return false.

If nums[i] > prev, we have a valid starting point. To be greedy, we want to modify nums[i] to be the smallest possible value that is still greater than prev. This is achieved by subtracting the largest possible prime p from nums[i] such that the result nums[i] - p is still greater than prev.

This condition nums[i] - p > prev is equivalent to p < nums[i] - prev. So, we need to find the largest prime p that is strictly less than the difference nums[i] - prev.

If such a prime exists, we subtract it from nums[i] to get the new value for the current position. If no such prime exists (e.g., if nums[i] - prev is 2 or less), we cannot make nums[i] any smaller, so we leave it as is.

We then update prev to this new, possibly modified value of nums[i] and proceed to the next element.

If we successfully process the entire array, it means a valid sequence can be formed, and we return true.

To efficiently find the 'largest prime less than k', we can pre-compute this information for all numbers up to the maximum possible value.

import java.util.Arrays; class Solution {    public boolean primeSubtraction(int[] nums) {        int maxVal = 1002; // Max possible value for num or diff + buffer        boolean[] isPrime = new boolean[maxVal];        Arrays.fill(isPrime, true);        isPrime[0] = isPrime[1] = false;        for (int p = 2; p * p < maxVal; p++) {            if (isPrime[p]) {                for (int i = p * p; i < maxVal; i += p) {                    isPrime[i] = false;                }            }        }         int[] largestPrimeSmallerThan = new int[maxVal];        // largestPrimeSmallerThan[k] stores the largest prime < k        for (int i = 3; i < maxVal; i++) {            if (isPrime[i - 1]) {                largestPrimeSmallerThan[i] = i - 1;            } else {                largestPrimeSmallerThan[i] = largestPrimeSmallerThan[i - 1];            }        }         int prev = 0;        for (int num : nums) {            if (num <= prev) {                return false;            }            int diff = num - prev;            int p = largestPrimeSmallerThan[diff];                        if (p > 0) {                prev = num - p;            } else {                prev = num;            }        }        return true;    }}

Complexity

Time

O(N + M log log M), where `N` is the length of `nums` and `M` is the maximum value (1000). The pre-computation takes `O(M log log M)` for the sieve and `O(M)` for the helper array. The main loop runs in `O(N)` time.

Space

O(M) to store the prime information and the `largestPrimeSmallerThan` array, where M is the maximum possible value in `nums` (around 1000).

Trade-offs

Pros

  • Very efficient in both time and space.

  • The greedy choice is simple and proven to be optimal for this problem.

Cons

  • The correctness of the greedy strategy is not immediately obvious without careful reasoning.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem