Problem of The Day: Prime Subtraction Operation

Problem Statement

Intuition

The problem requires modifying the elements in a list so that they form a strictly increasing sequence by subtracting prime numbers from each element. My initial intuition was to attempt a greedy approach. For each element, I could try to find the largest possible prime number to subtract, ensuring each element is less than the previous, thereby maintaining a strictly increasing order.

Approach

1. Copy the input list nums into a new list arr, where each element will be adjusted.
2. For each element in nums, find the largest prime number that can be subtracted to make arr[i] less than arr[i-1] (the previous element in arr).
   • Start with the largest possible candidate (num - 1) and decrement until finding a valid prime.
3. Update arr[i] after finding the prime that allows arr to remain strictly increasing up to that point.
4. After processing all elements, check if arr is strictly increasing. If so, return True; otherwise, return False.

Helper Functions

• isPrime(n): Checks if n is prime by verifying that no numbers between 2 and n-1 divide n.
• isStrictlyIncreaseOrder(nums): Ensures that the list nums is strictly increasing by comparing each element to the next.

Complexity

• Time Complexity:

  • Prime-checking function: (O(\sqrt{n})) for each check, repeated for each element in nums, so overall complexity depends on the size of primes tested.
  • Strictly increasing check: (O(n)).

• Space Complexity:

  • (O(n)) to store the modified array arr.

Code

class Solution:
    def primeSubOperation(self, nums: List[int]) -> bool:
        arr = nums[:]
        for i, num in enumerate(nums):
            curr = num - 1
            if i == 0:
                while curr >= 0 and not self.isPrime(curr):
                    curr -= 1
            else:
                while 0 < num - curr <= arr[i - 1] or not self.isPrime(curr):
                    curr -= 1

            if curr > 0:
                arr[i] = num - curr
            if self.isStrictlyIncreaseOrder(arr):
                return True

        return False

    def isPrime(self, n):
        if n == 0 or n == 1:
            return False

        for i in range(2, n):
            if n % i == 0:
                return False
        return True

    def isStrictlyIncreaseOrder(self, nums):
        for i in range(len(nums) - 1):
            if nums[i] >= nums[i + 1]:
                return False
        return True

Editorial

Approach 1: Brute Force

class Solution:
    def check_prime(self, x: int) -> bool:
        for i in range(2, int(x**0.5) + 1):
            if x % i == 0:
                return False
        return True

    def primeSubOperation(self, nums: List[int]) -> bool:
        for i in range(len(nums)):
            # In case of first index, we need to find the largest prime less than nums[0].
            if i == 0:
                bound = nums[0]
            else:
                # Otherwise, we need to find the largest prime, that makes the current element
                # closest to the previous element.
                bound = nums[i] - nums[i - 1]

            # If the bound is less than or equal to 0, then the array cannot be made strictly increasing.
            if bound <= 0:
                return False

            # Find the largest prime less than bound.
            largest_prime = 0
            for j in range(bound - 1, 1, -1):
                if self.check_prime(j):
                    largest_prime = j
                    break

            # Subtract this value from nums[i].
            nums[i] = nums[i] - largest_prime
        return True

• time: O(n * m*sqrt(m))
• space: O(1)

Approach 2: Storing the primes

class Solution:
    def isprime(self, n):
        for i in range(2, isqrt(n) + 1):
            if n % i == 0:
                return False
        return True

    def primeSubOperation(self, nums):
        maxElement = max(nums)

        # Store the previousPrime array.
        previous_prime = [0] * (maxElement + 1)
        for i in range(2, maxElement + 1):
            if self.isprime(i):
                previous_prime[i] = i
            else:
                previous_prime[i] = previous_prime[i - 1]

        for i in range(len(nums)):

            # In case of first index, we need to find the largest prime less
            # than nums[0].
            if i == 0:
                bound = nums[0]
            else:
                # Otherwise, we need to find the largest prime, that makes the
                # current element closest to the previous element.
                bound = nums[i] - nums[i - 1]

            # If the bound is less than or equal to 0, then the array cannot be
            # made strictly increasing.
            if bound <= 0:
                return False

            # Find the largest prime less than bound.
            largest_prime = previous_prime[bound - 1]

            # Subtract this value from nums[i].
            nums[i] -= largest_prime

        return True

Approach 3: Sieve of Eratosthenes + Two Pointers

class Solution:
    def primeSubOperation(self, nums):
        max_element = max(nums)

        # Store the sieve array.
        sieve = [1] * (max_element + 1)
        sieve[1] = 0
        for i in range(2, int(math.sqrt(max_element + 1)) + 1):
            if sieve[i] == 1:
                for j in range(i * i, max_element + 1, i):
                    sieve[j] = 0

        # Start by storing the currValue as 1, and the initial index as 0.
        curr_value = 1
        i = 0
        while i < len(nums):
            # Store the difference needed to make nums[i] equal to currValue.
            difference = nums[i] - curr_value

            # If difference is less than 0, then nums[i] is already less than
            # currValue. Return false in this case.
            if difference < 0:
                return False

            # If the difference is prime or zero, then nums[i] can be made
            # equal to currValue.
            if sieve[difference] or difference == 0:
                i += 1
                curr_value += 1
            else:
                # Otherwise, try for the next currValue.
                curr_value += 1
        return True