Prime Subtraction Operation

Prime Subtraction Operation

What is this problem about?

The Prime Subtraction Operation problem asks whether you can make an array strictly increasing by subtracting a prime from each element (at most once). For each element, you can optionally subtract any prime p < element to make the array strictly increasing. This coding problem uses binary search over precomputed primes. The array, math, number theory, binary search, and greedy interview pattern is the core.

Why is this asked in interviews?

Microsoft, Amazon, Google, and Bloomberg ask this because it tests greedy thinking with number theory: for each element, find the largest prime you can subtract (to make it as small as possible) while keeping it greater than the previous element.

Algorithmic pattern used

Greedy + precomputed primes + binary search. Precompute all primes up to max element using Sieve of Eratosthenes. Process elements greedily left to right: for each arr[i], find the largest prime p < arr[i] such that arr[i] - p > previous value. Use binary search on the sorted primes list. If no valid prime exists and arr[i] <= previous value, return false.

Example explanation

arr=[4,9,6,10]. prev=0.

• arr[0]=4: Need arr[0]-p > 0. Best: subtract 3 (prime) → 1 > 0 ✓. prev=1.
• arr[1]=9: Need 9-p > 1. Best: subtract 7 → 2 > 1 ✓. prev=2.
• arr[2]=6: Need 6-p > 2. Best primes < 6: 5→1≤2✗. 3→3>2 ✓. prev=3.
• arr[3]=10: Need 10-p > 3. Best: 5→5>3 ✓. Return true.

Common mistakes candidates make

• Not precomputing primes (trial division per element is too slow).
• Greedy without binary search (trying all primes linearly).
• Not checking that the subtracted prime is strictly less than the element.
• Not handling arr[i] <= prev without any prime to subtract (return false).

Interview preparation tip

Prime Subtraction combines Sieve of Eratosthenes with greedy binary search. The greedy insight: always subtract the largest valid prime (maximizes decrease while satisfying constraint). Binary search on sorted primes gives the optimal choice in O(log(max_prime)) per element. Practice problems combining prime generation with greedy array operations — they appear in optimization and scheduling contexts.