2601. Prime Subtraction Operation Solution

Q: Is Prime Subtraction Operation easy or hard?

Prime Subtraction Operation is rated Medium because it combines multiple concepts: greedy decisions, prime generation, and maintaining a strictly increasing sequence. The logic is simple once the greedy insight is clear, but recognizing the correct subtraction strategy requires careful reasoning.

Q: Prime Subtraction Operation Python/Java solution

Most implementations generate primes using the Sieve of Eratosthenes, then iterate through the array applying the greedy subtraction rule. The logic is straightforward to implement in Python, Java, C++, or JavaScript because it mainly involves array iteration, prime lookup, and binary search.

Q: How to solve Prime Subtraction Operation in O(n)?

Near linear performance is achieved by combining a greedy pass with precomputed primes. After building the prime list using a sieve, iterate through the array once and choose the largest valid prime less than the allowed difference. Each step performs constant or logarithmic work, making the overall runtime close to O(n).

Q: What is the best approach for Prime Subtraction Operation?

The most effective solution uses a greedy strategy combined with precomputed primes. Iterate through the array and subtract the largest prime that keeps the current value greater than the previous element. Precomputing primes with the Sieve of Eratosthenes and using binary search gives an efficient O(n log p) approach.

Q: Is Prime Subtraction Operation asked at Google/Amazon/Meta?

Problems combining greedy logic and number theory frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that involve prime preprocessing, array constraints, or monotonic sequences are common in technical screens.

Q: What data structure is used in Prime Subtraction Operation?

The solution primarily uses arrays and a list of prime numbers. The prime list is generated using a sieve and queried with binary search. The algorithm itself relies on greedy traversal of the input array.

Q: What is the time complexity of Prime Subtraction Operation?

The optimized solution runs in O(m log log m + n log p) time. The sieve step generates primes up to the maximum value m, and each array element performs a binary search among p primes. Space complexity is O(m) for storing the sieve or prime list.

The problem

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

Approach overview

Problem Overview: You receive an integer array nums. For each element, you may subtract a prime number smaller than the element at most once. The goal is to determine whether these operations can transform the array into a strictly increasing sequence.

Approach 1: Prime Subtraction Greedy Approach (O(n log p) time, O(p) space)

The core observation is that earlier elements should be minimized as much as possible so later elements have more room to remain larger. Iterate from left to right and maintain the previous valid value. For each nums[i], find the largest prime p such that nums[i] - p > prev. This keeps the new value just above the previous element while reducing the current number as much as possible. Store all primes up to the maximum array value and use binary search to quickly locate the largest valid prime. If no such prime exists and nums[i] <= prev, forming a strictly increasing sequence becomes impossible. This greedy strategy works because minimizing earlier numbers maximizes flexibility for the remaining elements.

Approach 2: Optimized Prime Sieve with Early Exit (O(m log log m + n log p) time, O(m) space)

Prime lookup becomes faster by generating all primes up to max(nums) using the Sieve of Eratosthenes from number theory. The sieve runs once in O(m log log m) where m is the largest number in the array. During the main pass, compute the difference diff = nums[i] - prev. Only primes smaller than diff are valid candidates. Use binary search over the prime list to pick the largest valid prime and subtract it. If nums[i] is already greater than prev, you may skip subtraction for efficiency. Add an early exit check whenever the current value cannot exceed prev. This approach combines greedy decision making with precomputed primes to keep each step efficient.

Recommended for interviews: Interviewers typically expect the greedy strategy with precomputed primes. A naive trial of primes per element shows understanding, but the optimized sieve + binary search demonstrates stronger algorithmic thinking. It combines array traversal, prime generation, and greedy decision making while maintaining near-linear performance.

Approach 1: Prime Subtraction Greedy Approach

The idea is to ensure every element is greater than its previous one by subtracting a suitable prime. We iterate through each element and subtract the smallest possible prime until the condition is met.

For each element in the array, find if there's a prime that can be subtracted to make the current element greater than the previous one. Repeat this for all elements until the array becomes strictly increasing.

Python

def is_prime(n):
  if n <= 1:
    return False
  if n <= 3:
    return True
  if n % 2 == 0 or n % 3 == 0:
    return False
  i = 5
  while i * i <= n:
    if n % i == 0 or n % (i + 2) == 0:
      return False
    i += 6
  return True


def can_be_strictly_increasing(nums):
  for i in range(1, len(nums)):
    if nums[i] <= nums[i - 1]:
      diff = nums[i] - nums[i - 1]
      for p in range(diff + 1, nums[i]):
        if is_prime(p):
          nums[i] -= p
          break
      if nums[i] <= nums[i - 1]:
        return False
  return True

nums = [4, 9, 6, 10]
print(can_be_strictly_increasing(nums))

Java

import java.util.*;

public class PrimeSubtraction {
  private static boolean isPrime(int num) {
    if (num <= 1) return false;
    if (num <= 3) return true;
    if (num % 2 == 0 || num % 3 == 0) return false;
    for (int i = 5; i * i <= num; i += 6) {
      if (num % i == 0 || num % (i + 2) == 0) return false;
    }
    return true;
  }

  public static boolean canBeStrictlyIncreasing(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
      if (nums[i] <= nums[i - 1]) {
        int diff = nums[i] - nums[i - 1];
        for (int p = diff + 1; p < nums[i]; p++) {
          if (isPrime(p)) {
            nums[i] -= p;
            break;
          }
        }
        if (nums[i] <= nums[i - 1]) {
          return false;
        }
      }
    }
    return true;
  }

  public static void main(String[] args) {
    int[] nums = {4, 9, 6, 10};
    System.out.println(canBeStrictlyIncreasing(nums));
  }
}

C++

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

bool is_prime(int number) {
  if (number <= 1) return false;
  for (int i = 2; i <= sqrt(number); i++) {
    if (number % i == 0) return false;
  }
  return true;
}

bool canBeeStrictlyIncreasing(vector<int>& nums) {
  for (int i = 1; i < nums.size(); ++i) {
    if (nums[i] <= nums[i - 1]) {
      int diff = nums[i] - nums[i - 1];
      bool found = false;

      for (int p = diff + 1; p < nums[i]; ++p) {
        if (is_prime(p)) {
          nums[i] -= p;
          found = true;
          break;
        }
      }

      if (!found || nums[i] <= nums[i - 1]) {
        return false;
      }
    }
  }
  return true;
}

int main() {
  vector<int> nums = {4, 9, 6, 10};
  if (canBeeStrictlyIncreasing(nums)) {
    cout << "true" << endl;
  } else {
    cout << "false" << endl;
  }
  return 0;
}

JavaScript

function isPrime(num) {
  if (num <= 1) return false;
  if (num <= 3) return true;
  if (num % 2 === 0 || num % 3 === 0) return false;
  let i = 5;
  while (i * i <= num) {
    if (num % i === 0 || num % (i + 2) === 0) return false;
    i += 6;
  }
  return true;
}

function canBeStrictlyIncreasing(nums) {
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] <= nums[i - 1]) {
      let diff = nums[i] - nums[i - 1];
      for (let p = diff + 1; p < nums[i]; p++) {
        if (isPrime(p)) {
          nums[i] -= p;
          break;
        }
      }
      if (nums[i] <= nums[i - 1]) {
        return false;
      }
    }
  }
  return true;
}

let nums = [4, 9, 6, 10];
console.log(canBeStrictlyIncreasing(nums));

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

bool isPrime(int n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (int i = 5; i * i <= n; i += 6) {
    if (n % i == 0 || n % (i + 2) == 0) return false;
  }
  return true;
}

bool canBeStrictlyIncreasing(int *nums, int n) {
  for (int i = 1; i < n; i++) {
    if (nums[i] <= nums[i - 1]) {
      int diff = nums[i] - nums[i - 1];
      for (int p = diff + 1; p < nums[i]; p++) {
        if (isPrime(p)) {
          nums[i] -= p;
          break;
        }
      }
      if (nums[i] <= nums[i - 1]) {
        return false;
      }
    }
  }
  return true;
}

int main() {
  int nums[] = {4, 9, 6, 10};
  int n = sizeof(nums) / sizeof(nums[0]);
  if (canBeStrictlyIncreasing(nums, n)) {
    printf("true\n");
  } else {
    printf("false\n");
  }
  return 0;
}

using System;

public class PrimeSubtraction {
  public static bool IsPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6) {
      if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
  }

  public static bool CanBeStrictlyIncreasing(int[] nums) {
    for (int i = 1; i < nums.Length; i++) {
      if (nums[i] <= nums[i - 1]) {
        int diff = nums[i] - nums[i - 1];
        for (int p = diff + 1; p < nums[i]; p++) {
          if (IsPrime(p)) {
            nums[i] -= p;
            break;
          }
        }
        if (nums[i] <= nums[i - 1]) {
          return false;
        }
      }
    }
    return true;
  }

  public static void Main() {
    int[] nums = {4, 9, 6, 10};
    Console.WriteLine(CanBeStrictlyIncreasing(nums));
  }
}

The Python solution ensures that for every consecutive element, the array maintains strict increasing order by decreasing the current element using the smallest possible prime number.

Complexity

Time Complexity: O(n * log(n)), proportional to the inner prime evaluation.
Space Complexity: O(1), since the operations are performed in place.

Try this approach in the editor

Approach 2: Optimized Prime Sieve with Early Exit

This approach involves using the Sieve of Eratosthenes to precompute primes up to the maximum value in the array. For each element, we maintain a list of unpicked primes smaller than the current number and dynamically reduce the current element with the largest viable prime, proceeding until a strictly increasing order is established.

We use this optimized list to attempt to produce a valid increasing order to minimize operation count and improve efficiency.

Python

def sieve(n):
  is_prime = [True] * (n + 1)
  is_prime[0] = is_prime[1] = False
  for i in range(2, int(n**0.5) + 1):
    if is_prime[i]:
      for j in range(i * i, n + 1, i):
        is_prime[j] = False
  return is_prime


def can_be_strictly_increasing(nums):
  is_prime = sieve(1000)
  for i in range(1, len(nums)):
    if nums[i] <= nums[i - 1]:
      diff = nums[i] - nums[i - 1]
      for p in range(diff + 1, nums[i]):
        if is_prime[p]:
          nums[i] -= p
          break
      if nums[i] <= nums[i - 1]:
        return False
  return True

nums = [4, 9, 6, 10]
print(can_be_strictly_increasing(nums))

Java

import java.util.*;

public class PrimeSubtraction {
  public static void sieve(int max, boolean[] isPrime) {
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;
    for (int p = 2; p * p <= max; ++p) {
      if (isPrime[p]) {
        for (int i = p * p; i <= max; i += p) {
          isPrime[i] = false;
        }
      }
    }
  }

  public static boolean canBeStrictlyIncreasing(int[] nums) {
    boolean[] isPrime = new boolean[1001];
    sieve(1000, isPrime);
    for (int i = 1; i < nums.length; ++i) {
      if (nums[i] <= nums[i - 1]) {
        int diff = nums[i] - nums[i - 1];
        for (int p = diff + 1; p < nums[i]; ++p) {
          if (isPrime[p]) {
            nums[i] -= p;
            break;
          }
        }
        if (nums[i] <= nums[i - 1]) {
          return false;
        }
      }
    }
    return true;
  }

  public static void main(String[] args) {
    int[] nums = {4, 9, 6, 10};
    System.out.println(canBeStrictlyIncreasing(nums));
  }
}

C++

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

void sieve(int max, vector<bool>& is_prime) {
  is_prime.assign(max + 1, true);
  is_prime[0] = is_prime[1] = false;
  for (int p = 2; p * p <= max; ++p) {
    if (is_prime[p]) {
      for (int i = p * p; i <= max; i += p) {
        is_prime[i] = false;
      }
    }
  }
}

bool canBeeStrictlyIncreasing(vector<int>& nums) {
  vector<bool> is_prime;
  sieve(1000, is_prime);
  for (int i = 1; i < nums.size(); ++i) {
    if (nums[i] <= nums[i - 1]) {
      int diff = nums[i] - nums[i - 1];
      for (int p = diff + 1; p < nums[i]; ++p) {
        if (is_prime[p]) {
          nums[i] -= p;
          break;
        }
      }
      if (nums[i] <= nums[i - 1]) {
        return false;
      }
    }
  }
  return true;
}

int main() {
  vector<int> nums = {4, 9, 6, 10};
  if (canBeeStrictlyIncreasing(nums)) {
    cout << "true" << endl;
  } else {
    cout << "false" << endl;
  }
  return 0;
}

JavaScript

function sieve(n) {
  const isPrime = Array(n + 1).fill(true);
  isPrime[0] = isPrime[1] = false;
  for (let i = 2; i * i <= n; i++) {
    if (isPrime[i]) {
      for (let j = i * i; j <= n; j += i) {
        isPrime[j] = false;
      }
    }
  }
  return isPrime;
}

function canBeStrictlyIncreasing(nums) {
  const isPrime = sieve(1000);
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] <= nums[i - 1]) {
      let diff = nums[i] - nums[i - 1];
      for (let p = diff + 1; p < nums[i]; p++) {
        if (isPrime[p]) {
          nums[i] -= p;
          break;
        }
      }
      if (nums[i] <= nums[i - 1]) {
        return false;
      }
    }
  }
  return true;
}

let nums = [4, 9, 6, 10];
console.log(canBeStrictlyIncreasing(nums));

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

void sieve(int n, bool *is_prime) {
  memset(is_prime, true, sizeof(bool) * (n + 1));
  is_prime[0] = is_prime[1] = false;
  for (int p = 2; p * p <= n; p++) {
    if (is_prime[p]) {
      for (int i = p * p; i <= n; i += p)
        is_prime[i] = false;
    }
  }
}

bool canBeStrictlyIncreasing(int *nums, int n) {
  bool isPrime[1001];
  sieve(1000, isPrime);
  for (int i = 1; i < n; i++) {
    if (nums[i] <= nums[i - 1]) {
      int diff = nums[i] - nums[i - 1];
      for (int p = diff + 1; p < nums[i]; p++) {
        if (isPrime[p]) {
          nums[i] -= p;
          break;
        }
      }
      if (nums[i] <= nums[i - 1]) {
        return false;
      }
    }
  }
  return true;
}

int main() {
  int nums[] = {4, 9, 6, 10};
  int n = sizeof(nums) / sizeof(nums[0]);
  if (canBeStrictlyIncreasing(nums, n)) {
    printf("true\n");
  } else {
    printf("false\n");
  }
  return 0;
}

using System;

public class PrimeSubtraction {
  public static void Sieve(int max, bool[] isPrime) {
    Array.Fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;
    for (int p = 2; p * p <= max; ++p) {
      if (isPrime[p]) {
        for (int i = p * p; i <= max; i += p) {
          isPrime[i] = false;
        }
      }
    }
  }

  public static bool CanBeStrictlyIncreasing(int[] nums) {
    bool[] isPrime = new bool[1001];
    Sieve(1000, isPrime);
    for (int i = 1; i < nums.Length; ++i) {
      if (nums[i] <= nums[i - 1]) {
        int diff = nums[i] - nums[i - 1];
        for (int p = diff + 1; p < nums[i]; ++p) {
          if (isPrime[p]) {
            nums[i] -= p;
            break;
          }
        }
        if (nums[i] <= nums[i - 1]) {
          return false;
        }
      }
    }
    return true;
  }

  public static void Main() {
    int[] nums = {4, 9, 6, 10};
    Console.WriteLine(CanBeStrictlyIncreasing(nums));
  }
}

Python solution integrates the sieve for preliminary prime computation to streamline runtime for seeking operations that ultimately maintain array growth habit.

Complexity

Time Complexity: O(n * sqrt(m)) for the primality check during operations bounded by maximum element range.
Space Complexity: O(m), making use of the calculated primes storage.

Try this approach in the editor

Approach 3: 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.

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

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
}

Try this approach in the editor

Approach 4: 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;
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Prime Subtraction Greedy Approach	Time Complexity: O(n * log(n)), proportional to the inner prime evaluation. Space Complexity: O(1), since the operations are performed in place.
Optimized Prime Sieve with Early Exit	Time Complexity: O(n * sqrt(m)) for the primality check during operations bounded by maximum element range. Space Complexity: O(m), making use of the calculated primes storage.
Preprocessing prime numbers + binary search	–
Preprocessing prime numbers	–

Complexity analysis

Approach	Time	Space	When to Use
Prime Subtraction Greedy with Binary Search	O(n log p)	O(p)	General case when primes are precomputed and you need efficient lookups
Optimized Prime Sieve with Early Exit	O(m log log m + n log p)	O(m)	Best for repeated prime queries or large arrays where fast prime generation helps

Frequently asked questions

Is Prime Subtraction Operation easy or hard?

Prime Subtraction Operation is rated Medium because it combines multiple concepts: greedy decisions, prime generation, and maintaining a strictly increasing sequence. The logic is simple once the greedy insight is clear, but recognizing the correct subtraction strategy requires careful reasoning.

Prime Subtraction Operation Python/Java solution

Most implementations generate primes using the Sieve of Eratosthenes, then iterate through the array applying the greedy subtraction rule. The logic is straightforward to implement in Python, Java, C++, or JavaScript because it mainly involves array iteration, prime lookup, and binary search.

How to solve Prime Subtraction Operation in O(n)?

Near linear performance is achieved by combining a greedy pass with precomputed primes. After building the prime list using a sieve, iterate through the array once and choose the largest valid prime less than the allowed difference. Each step performs constant or logarithmic work, making the overall runtime close to O(n).

What is the best approach for Prime Subtraction Operation?

The most effective solution uses a greedy strategy combined with precomputed primes. Iterate through the array and subtract the largest prime that keeps the current value greater than the previous element. Precomputing primes with the Sieve of Eratosthenes and using binary search gives an efficient O(n log p) approach.

Is Prime Subtraction Operation asked at Google/Amazon/Meta?

Problems combining greedy logic and number theory frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that involve prime preprocessing, array constraints, or monotonic sequences are common in technical screens.

What data structure is used in Prime Subtraction Operation?

The solution primarily uses arrays and a list of prime numbers. The prime list is generated using a sieve and queried with binary search. The algorithm itself relies on greedy traversal of the input array.

What is the time complexity of Prime Subtraction Operation?

The optimized solution runs in O(m log log m + n log p) time. The sieve step generates primes up to the maximum value m, and each array element performs a binary search among p primes. Space complexity is O(m) for storing the sieve or prime list.

Prime Subtraction Operation solution and explanation

The problem

Approach overview

Approach 1: Prime Subtraction Greedy Approach

Approach 2: Optimized Prime Sieve with Early Exit

Approach 3: Preprocessing prime numbers + binary search

Approach 4: Preprocessing prime numbers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Prime Subtraction Operation solution and explanation

The problem

Approach overview

Approach 1: Prime Subtraction Greedy Approach

Approach 2: Optimized Prime Sieve with Early Exit

Approach 3: Preprocessing prime numbers + binary search

Approach 4: Preprocessing prime numbers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems