We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Prime Subtraction Operation

Number: 2716

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a 0-indexed integer array nums, you may perform the following operation at most once per index: choose an index i (that you haven’t picked before) and subtract from nums[i] any prime number p that is strictly less than nums[i]. Determine if it is possible to perform these operations (in any order) so that the resulting array is strictly increasing.

Key Insights

  • For each element, the set of possible new values is {nums[i]} ∪ {nums[i] - p for every prime p < nums[i]}.
  • We need to form a strictly increasing sequence; hence, if we denote the chosen value for index i as a_i, then a0 < a1 < ... < a_(n-1).
  • A greedy strategy works: Process the array from left to right. For each element, choose the smallest possible value (from its available options) that is strictly greater than the previously chosen value. This minimizes the current value and gives maximum flexibility for subsequent choices.
  • Precompute the list of primes up to 1000 (since nums[i] <= 1000) so that for any nums[i] you can quickly enumerate valid subtracted outcomes.

Space and Time Complexity

Time Complexity: O(n * k) where n is the number of elements (up to 1000) and k is the number of primes up to 1000 (roughly up to 168).
Space Complexity: O(n + P) where P is the number of primes computed (negligible compared to n).

Solution

We first precompute all primes up to the maximum possible value (1000) using a sieve algorithm. For each number in nums, compute its candidate outcomes: either leave it unchanged or subtract any prime p (p < nums[i]). Then iterate from left to right with a variable (prev) that stores the last chosen value. For each nums[i], take its candidate set, sort it in increasing order, and choose the smallest candidate that is strictly greater than prev. If no such candidate exists, then it is impossible to construct a strictly increasing sequence. Otherwise, update prev and continue. Finally, if all elements are assigned a valid new value, return true.

Code Solutions

# Python solution with line-by-line comments

def sieve(n):
    # Sieve of Eratosthenes to generate primes up to 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 list of all primes <= n.
    return [i for i, prime in enumerate(is_prime) if prime]

def primeSubOperation(nums):
    # Precompute primes up to max number in nums (or 1000)
    max_val = 1000  
    primes = sieve(max_val)
    
    # The greedy strategy: process from left to right.
    prev = -float('inf')  # initial previous chosen value
    for num in nums:
        candidates = set()
        # Option of not performing operation.
        candidates.add(num)
        # Add all possible outcomes by subtracting a prime p if p < num.
        for p in primes:
            if p < num:
                candidates.add(num - p)
            else:
                break  # since primes is sorted, no need to check further
        # Sort candidates so we can pick the smallest value > prev.
        sorted_candidates = sorted(candidates)
        found = False
        for candidate in sorted_candidates:
            if candidate > prev:
                prev = candidate
                found = True
                break
        if not found:
            return False  # if no candidate is found, sequence cannot be strictly increasing
    return True

# Example usage:
print(primeSubOperation([4, 9, 6, 10]))  # Expected output: True
print(primeSubOperation([6, 8, 11, 12])) # Expected output: True
print(primeSubOperation([5, 8, 3]))      # Expected output: False
← Back to All Questions