Prime Subtraction Operation - Practice Coding Problems

Prime Subtraction Operation - Problem

Array Math Binary Search Greedy Number Theory Medium

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.

A strictly increasing array is an array whose each element is strictly greater than its preceding element.

Input & Output

Example 1 — Possible Case

$ Input: nums = [4,9,6,10]

› Output: true

💡 Note: We can subtract prime 2 from 4 to get [2,9,6,10], then subtract prime 7 from 9 to get [2,2,6,10], but 2=2 violates strictly increasing. Actually, we need different approach: subtract 2 from 4→2, subtract 5 from 6→1, but then 9>1 so subtract more from 9. The greedy approach working right-to-left would determine feasibility.

Example 2 — Already Increasing

$ Input: nums = [6,8,11,12]

› Output: true

💡 Note: Array is already strictly increasing: 6 < 8 < 11 < 12, so no operations needed.

Example 3 — Impossible Case

$ Input: nums = [5,8,3]

› Output: false

💡 Note: We need 5 < something < 3, but after subtracting any prime from 8, we cannot make 8 less than 3 while keeping 5 less than the result.

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ nums[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Array

[4,9,6,10] - not strictly increasing

Prime Operations

Subtract primes to fix ordering: work right-to-left

Result

Determine if strictly increasing arrangement possible

Key Takeaway

🎯 Key Insight: Work backwards through the array, making each element as small as possible while maintaining order

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to work backwards (right-to-left) through the array, making each element as small as possible while maintaining strictly increasing order. The greedy approach with pre-computed primes using Sieve of Eratosthenes provides the optimal solution. Time: O(max_val × log(log(max_val)) + n × log(π(max_val))), Space: O(max_val)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized with Sieve	O(max_val × log(log(max_val)) + n × log(π(max_val)))	O(max_val)	Pre-compute primes using Sieve of Eratosthenes for efficiency
Greedy Right-to-Left	O(n × √max_val)	O(1)	Work backwards, keeping each element as small as possible
Brute Force Recursive	O(2^n)	O(n)	Try all possible prime subtractions recursively

Optimized with Sieve — Algorithm Steps

Pre-compute all primes using Sieve of Eratosthenes
Work backwards through array
For each element, find optimal prime to subtract
Use binary search on primes for efficiency

Visualization

Tap to expand

Step-by-Step Walkthrough

Sieve Generation

Pre-compute all primes up to max value

Binary Search

Quickly find suitable primes for each element

Apply Changes

Efficiently modify array working right-to-left

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(int* nums, int len) {
    if (len == 0) return true;
    
    int maxVal = 0;
    for (int i = 0; i < len; i++) {
        if (nums[i] > maxVal) maxVal = nums[i];
    }
    
    // Sieve of Eratosthenes
    bool* isPrime = malloc((maxVal + 1) * sizeof(bool));
    for (int i = 0; i <= maxVal; i++) isPrime[i] = true;
    isPrime[0] = isPrime[1] = false;
    
    for (int i = 2; i * i <= maxVal; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= maxVal; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    int* primes = malloc(maxVal * sizeof(int));
    int primeCount = 0;
    for (int i = 2; i <= maxVal; i++) {
        if (isPrime[i]) primes[primeCount++] = i;
    }
    
    // Work from right to left
    for (int i = len - 2; i >= 0; i--) {
        if (nums[i] < nums[i + 1]) continue;
        
        // Find largest prime we can subtract to get < nums[i + 1]
        int target = nums[i + 1] - 1;
        int minNeeded = nums[i] - target;
        
        // Linear search for smallest prime >= minNeeded
        int idx = 0;
        while (idx < primeCount && primes[idx] < minNeeded) idx++;
        
        bool found = false;
        while (idx < primeCount && primes[idx] < nums[i]) {
            int newVal = nums[i] - primes[idx];
            if (newVal <= target && newVal > 0) {
                nums[i] = newVal;
                found = true;
                break;
            }
            idx++;
        }
        
        if (!found) {
            free(isPrime);
            free(primes);
            return false;
        }
    }
    
    free(isPrime);
    free(primes);
    return true;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int nums[100];
    int len = 0;
    char* token = strtok(line + 1, ",]");
    while (token) {
        nums[len++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    bool result = solution(nums, len);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(max_val × log(log(max_val)) + n × log(π(max_val)))

Sieve takes O(max_val × log(log(max_val))), then O(n × log(π(max_val))) for binary searches

⚡ Linearithmic

Space Complexity

O(max_val)

Sieve array and prime list storage proportional to maximum value

✓ Linear Space

12.4K Views

Medium Frequency

~25 min Avg. Time

287 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized with Sieve — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler