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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Prime Subtraction Operation

Difficulty: Medium

Problem Description

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.

Key Insights

  • A strictly increasing array requires that each element is greater than the one before it.
  • Prime numbers are the only valid values that can be subtracted from each element.
  • If an element is greater than the next element, it may need to be reduced using a prime number.
  • The largest prime number below any number can be efficiently found using a precomputed list of primes or a prime-checking function.
  • The process can be approached greedily, starting from the leftmost element and ensuring each element is less than the next.

Space and Time Complexity

Time Complexity: O(n * log(max)), where n is the number of elements in nums and max is the maximum value in nums.
Space Complexity: O(max) for storing prime numbers.

Solution

The solution involves iterating through the list of numbers from left to right, ensuring that each number can be made strictly less than the next using valid prime subtractions. We can precompute all prime numbers up to the maximum possible value (1000 in this case) using the Sieve of Eratosthenes. For each number, we will check if it can be reduced to a value lower than the next one while still being a valid prime subtraction.

Code Solutions

def isStrictlyIncreasing(nums):
    def sieve_of_eratosthenes(max_num):
        primes = []
        is_prime = [True] * (max_num + 1)
        for p in range(2, max_num + 1):
            if is_prime[p]:
                primes.append(p)
                for multiple in range(p * 2, max_num + 1, p):
                    is_prime[multiple] = False
        return primes
    
    max_value = max(nums)
    primes = sieve_of_eratosthenes(max_value)
    n = len(nums)

    for i in range(n - 1):
        if nums[i] >= nums[i + 1]:
            # We need to reduce nums[i] to be less than nums[i + 1]
            target = nums[i + 1]
            max_prime_to_subtract = -1
            
            # Find the largest prime less than nums[i]
            for prime in primes:
                if prime < nums[i]:
                    max_prime_to_subtract = prime
                else:
                    break
            
            # Check if we can reduce nums[i] to be less than target
            if nums[i] - max_prime_to_subtract >= target:
                return False
            else:
                nums[i] -= max_prime_to_subtract
    
    return True
← Back to All Questions