Prime Subtraction Operation

medium greedy primes binary search

Problem

You are given a 0-indexed integer array nums. Any number of times you may pick an index you haven't picked before and a prime p strictly less than nums[i], then subtract p from nums[i]. Return true if you can make nums strictly increasing, and false otherwise.

Inputnums = [4, 9, 6, 10]

Outputtrue

Subtract 3 from index 0 → 1, and 7 from index 1 → 2, giving [1, 2, 6, 10], which is strictly increasing.

nums (comma-separated, 1..1000)

def primeSubOperation(nums):
    # Sieve of Eratosthenes for all primes up to 1000.
    is_prime = [True] * 1001
    is_prime[0] = is_prime[1] = False
    for i in range(2, 32):
        if is_prime[i]:
            for j in range(i * i, 1001, i):
                is_prime[j] = False
    primes = [i for i in range(2, 1001) if is_prime[i]]

    prev = 0                       # value fixed for the previous index
    for x in nums:
        # Largest prime p < x - prev makes x - p as small as possible
        # while still > prev. bisect_left finds that prime in O(log).
        lo, hi, p = 0, len(primes) - 1, 0
        while lo <= hi:
            mid = (lo + hi) // 2
            if primes[mid] < x - prev:
                p = primes[mid]    # candidate, keep searching right
                lo = mid + 1
            else:
                hi = mid - 1
        v = x - p                  # smallest reachable value > prev
        if v <= prev:              # cannot beat the previous element
            return False
        prev = v
    return True

function primeSubOperation(nums) {
  // Sieve of Eratosthenes for all primes up to 1000.
  const isPrime = new Array(1001).fill(true);
  isPrime[0] = isPrime[1] = false;
  for (let i = 2; i < 32; i++) {
    if (isPrime[i]) {
      for (let j = i * i; j <= 1000; j += i) isPrime[j] = false;
    }
  }
  const primes = [];
  for (let i = 2; i <= 1000; i++) if (isPrime[i]) primes.push(i);

  let prev = 0;                      // value fixed for the previous index
  for (const x of nums) {
    // Largest prime p < x - prev makes x - p as small as possible
    // while still > prev. Binary search finds that prime.
    let lo = 0, hi = primes.length - 1, p = 0;
    while (lo <= hi) {
      const mid = (lo + hi) >> 1;
      if (primes[mid] < x - prev) { p = primes[mid]; lo = mid + 1; }
      else hi = mid - 1;
    }
    const v = x - p;                 // smallest reachable value > prev
    if (v <= prev) return false;      // cannot beat the previous element
    prev = v;
  }
  return true;
}

boolean primeSubOperation(int[] nums) {
    // Sieve of Eratosthenes for all primes up to 1000.
    boolean[] isPrime = new boolean[1001];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i < 32; i++)
        if (isPrime[i])
            for (int j = i * i; j <= 1000; j += i) isPrime[j] = false;
    List<Integer> primes = new ArrayList<>();
    for (int i = 2; i <= 1000; i++) if (isPrime[i]) primes.add(i);

    int prev = 0;                      // value fixed for the previous index
    for (int x : nums) {
        // Largest prime p < x - prev makes x - p as small as possible
        // while still > prev. Binary search finds that prime.
        int lo = 0, hi = primes.size() - 1, p = 0;
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            if (primes.get(mid) < x - prev) { p = primes.get(mid); lo = mid + 1; }
            else hi = mid - 1;
        }
        int v = x - p;                 // smallest reachable value > prev
        if (v <= prev) return false;    // cannot beat the previous element
        prev = v;
    }
    return true;
}

bool primeSubOperation(vector<int>& nums) {
    // Sieve of Eratosthenes for all primes up to 1000.
    vector<bool> isPrime(1001, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i < 32; i++)
        if (isPrime[i])
            for (int j = i * i; j <= 1000; j += i) isPrime[j] = false;
    vector<int> primes;
    for (int i = 2; i <= 1000; i++) if (isPrime[i]) primes.push_back(i);

    int prev = 0;                      // value fixed for the previous index
    for (int x : nums) {
        // Largest prime p < x - prev makes x - p as small as possible
        // while still > prev. Binary search finds that prime.
        int lo = 0, hi = (int)primes.size() - 1, p = 0;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (primes[mid] < x - prev) { p = primes[mid]; lo = mid + 1; }
            else hi = mid - 1;
        }
        int v = x - p;                 // smallest reachable value > prev
        if (v <= prev) return false;    // cannot beat the previous element
        prev = v;
    }
    return true;
}

Explanation

This is a greedy problem. We sweep left to right and, for each element, make it as small as possible while keeping the array strictly increasing so far. Leaving an element as low as we legally can gives the next element the most room to fit above it.

Subtracting a prime p < nums[i] turns nums[i] into nums[i] - p. To make the result small but still greater than prev (the value we just fixed for the previous index), we want the largest prime that satisfies nums[i] - p > prev, i.e. p < nums[i] - prev. The bigger the prime we subtract, the lower the new value.

We precompute every prime up to 1000 with a Sieve of Eratosthenes, then use binary search to find the largest prime strictly less than nums[i] - prev. If no such prime exists, we subtract nothing (p = 0) and keep the element unchanged.

After choosing the value v = nums[i] - p, if v <= prev the array cannot be made strictly increasing and we return false. Otherwise we set prev = v and continue.

Example: [4, 9, 6, 10]. Index 0: prev = 0, largest prime < 4 is 3, so 4 → 1. Index 1: largest prime < 9 - 1 = 8 is 7, so 9 → 2. Index 2: x = 6, prev = 2, largest prime < 6 - 2 = 4 is 3, so 6 → 3 (3 > 2 ✓). Index 3: x = 10, prev = 3, largest prime < 10 - 3 = 7 is 5, so 10 → 5 (5 > 3 ✓). Final [1, 2, 3, 5] is strictly increasing → true.

Time: O(M log log M + n log P) Space: O(M)