Problem Description

You are given an integer array nums.

A proper divisor of a natural number x is any positive divisor that is strictly less than x. For example, 2 is a proper divisor of 4 (since 2 divides 4 and 2 < 4), while 6 is not a proper divisor of 6 (since 6 is not less than 6).

You can perform operations on the array where each operation consists of:

1. Select any one element from nums
2. Divide it by its greatest proper divisor

Your goal is to make the array non-decreasing (each element is less than or equal to the next element) using the minimum number of operations.

Return the minimum number of operations needed to achieve this. If it's impossible to make the array non-decreasing, return -1.

Key insights about the operation:

• When you divide a number by its greatest proper divisor, you're essentially finding the smallest value that number can become through this operation
• For a prime number p, the greatest proper divisor is 1, so p / 1 = p (no change)
• For a composite number n, dividing by its greatest proper divisor gives you the smallest prime factor of n

Example scenarios:

• If a number is 12, its proper divisors are {1, 2, 3, 4, 6}. The greatest is 6, so 12 / 6 = 2
• If a number is 7 (prime), its only proper divisor is 1, so 7 / 1 = 7 (unchanged)

The strategy involves checking from right to left: if an element is greater than the next element, try to reduce it using the operation. If even after reduction it's still greater than the next element, the task is impossible.

Intuition

The key observation is understanding what happens when we divide a number by its greatest proper divisor.

For any composite number n, if we divide it by its greatest proper divisor, we get the smallest prime factor of n. Why? Because if n = p × q where p is the smallest prime factor, then q must be the greatest proper divisor. So n / q = p.

For a prime number, the only proper divisor is 1, so dividing by 1 doesn't change the number. This means once a number becomes prime, it cannot be reduced further.

Now, when should we apply operations? We want a non-decreasing array with minimum operations. A greedy approach makes sense: only change a number when absolutely necessary.

Working from right to left is crucial here. Why? Because:

• The rightmost element sets a constraint for elements to its left
• If we need to reduce an element, we want to know the maximum value it needs to be less than or equal to
• By processing right to left, we always know what constraint the current element must satisfy

When we encounter nums[i] > nums[i+1], we must reduce nums[i]. The operation converts it to its smallest prime factor (if it's composite) or keeps it unchanged (if it's prime). This is the only possible reduction for that number.

If after this single reduction nums[i] is still greater than nums[i+1], we know it's impossible to fix the array. Why? Because we've already applied the maximum possible reduction to that element - it's now either unchanged (was prime) or has become its smallest prime factor (was composite), and we can't reduce it any further.

This leads to preprocessing: we compute the smallest prime factor for all possible numbers using a sieve-like approach. Then we traverse right to left, applying the reduction only when needed, counting operations along the way.

Learn more about Greedy and Math patterns.

Solution Approach

The solution consists of two main parts: preprocessing to find the smallest prime factor for each number, and then applying a greedy algorithm from right to left.

Step 1: Preprocessing - Finding Smallest Prime Factors

We create an array lpf (least prime factor) where lpf[i] stores the smallest prime factor of i. The preprocessing uses a sieve-like approach:

mx = 10**6 + 1
lpf = [0] * (mx + 1)
for i in range(2, mx + 1):
    if lpf[i] == 0:  # i is prime
        for j in range(i, mx + 1, i):
            if lpf[j] == 0:  # j hasn't been assigned a prime factor yet
                lpf[j] = i

• We iterate through numbers from 2 to mx
• If lpf[i] == 0, then i is prime (hasn't been marked by any smaller prime)
• For each prime i, we mark all its multiples j with lpf[j] = i (but only if j hasn't been marked yet, ensuring we get the smallest prime factor)

Step 2: Greedy Algorithm from Right to Left

Once we have the smallest prime factors, we traverse the array from right to left:

def minOperations(self, nums: List[int]) -> int:
    ans = 0
    for i in range(len(nums) - 2, -1, -1):
        if nums[i] > nums[i + 1]:
            nums[i] = lpf[nums[i]]  # Replace with smallest prime factor
            if nums[i] > nums[i + 1]:  # Still greater? Impossible!
                return -1
            ans += 1
    return ans

The algorithm works as follows:

1. Start from the second-to-last element and move leftward
2. At each position i, check if nums[i] > nums[i + 1]
3. If yes, we must reduce nums[i] by replacing it with its smallest prime factor: nums[i] = lpf[nums[i]]
4. After reduction, check again if nums[i] > nums[i + 1]
   • If still greater, return -1 (impossible to make non-decreasing)
   • Otherwise, increment the operation count
5. Continue until all elements are processed

Why This Works:

• When we divide a number by its greatest proper divisor, we get its smallest prime factor
• Each element can only be reduced once (to its smallest prime factor if composite, or stays same if prime)
• By processing right to left, we ensure we make the minimum necessary changes
• If an element can't be made small enough even after reduction, the task is impossible

Time Complexity:

• Preprocessing: O(n log log n) for the sieve
• Main algorithm: O(m) where m is the length of the input array
• Overall: O(n log log n + m) where n is the maximum possible value in the array

Example Walkthrough

Let's walk through the solution with nums = [25, 7, 14, 10].

Step 1: Precompute smallest prime factors

• For 25: 25 = 5 × 5, so lpf[25] = 5
• For 7: 7 is prime, so lpf[7] = 7
• For 14: 14 = 2 × 7, so lpf[14] = 2
• For 10: 10 = 2 × 5, so lpf[10] = 2

Step 2: Process array from right to left

Starting position: [25, 7, 14, 10], operations = 0

i = 2 (comparing 14 and 10):

• Is 14 > 10? Yes, we need to reduce 14
• Apply operation: 14 → lpf[14] = 2
• Array becomes: [25, 7, 2, 10]
• Is 2 > 10? No, we're good
• operations = 1

i = 1 (comparing 7 and 2):

• Is 7 > 2? Yes, we need to reduce 7
• Apply operation: 7 → lpf[7] = 7 (stays the same, it's prime!)
• Array remains: [25, 7, 2, 10]
• Is 7 still > 2? Yes! This means it's impossible
• Return -1

The array cannot be made non-decreasing because 7 is prime and cannot be reduced further, yet it needs to be ≤ 2.

Let's try another example where it's possible: nums = [15, 20, 10]

Step 1: Precompute smallest prime factors

• lpf[15] = 3 (15 = 3 × 5)
• lpf[20] = 2 (20 = 2 × 10)
• lpf[10] = 2 (10 = 2 × 5)

Step 2: Process array from right to left

Starting position: [15, 20, 10], operations = 0

i = 1 (comparing 20 and 10):

• Is 20 > 10? Yes, we need to reduce 20
• Apply operation: 20 → lpf[20] = 2
• Array becomes: [15, 2, 10]
• Is 2 > 10? No, we're good
• operations = 1

i = 0 (comparing 15 and 2):

• Is 15 > 2? Yes, we need to reduce 15
• Apply operation: 15 → lpf[15] = 3
• Array becomes: [3, 2, 10]
• Is 3 > 2? Yes! This is still greater
• Return -1

Even this array cannot be made non-decreasing!

Final example where it works: nums = [4, 3, 10]

Step 1: Precompute smallest prime factors

• lpf[4] = 2 (4 = 2 × 2)
• lpf[3] = 3 (3 is prime)
• lpf[10] = 2 (10 = 2 × 5)

Step 2: Process array from right to left

Starting position: [4, 3, 10], operations = 0

i = 1 (comparing 3 and 10):

• Is 3 > 10? No, already in order
• No operation needed

i = 0 (comparing 4 and 3):

• Is 4 > 3? Yes, we need to reduce 4
• Apply operation: 4 → lpf[4] = 2
• Array becomes: [2, 3, 10]
• Is 2 > 3? No, we're good
• operations = 1

Final array: [2, 3, 10] (non-decreasing) Return: 1 operation

Solution Implementation

Time and Space Complexity

The code consists of two parts: preprocessing to compute the least prime factor (LPF) array and the main solution.

Preprocessing Time Complexity: O(M × log log M), where M = 10^6. This uses a modified Sieve of Eratosthenes approach. For each prime number i, we iterate through its multiples up to M. The total number of operations is approximately M × (1/2 + 1/3 + 1/5 + 1/7 + ... ) for all primes up to M, which equals O(M × log log M).

Main Solution Time Complexity: O(n), where n is the length of the input array nums. The algorithm performs a single backward traversal through the array, with each element being processed in constant time (looking up lpf[nums[i]] is O(1)).

Overall Time Complexity: O(M × log log M + n), dominated by the preprocessing step since M is a large constant.

Space Complexity: O(M), where M = 10^6 + 1. The space is primarily used for the lpf array which stores the least prime factor for each number from 0 to M. The additional space used by the solution method is negligible compared to this.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Understanding of the Operation

Pitfall: Many developers mistakenly think they can repeatedly apply the operation to the same element multiple times to reduce it further. For example, thinking that 12 → 2 → 2 (applying operation twice).

Why it's wrong: Each element can only be operated on once. When you divide a number by its greatest proper divisor, you get its smallest prime factor, which is either prime itself or stays unchanged if already prime. You cannot reduce it further.

Solution: Remember that each element has at most one transformation:

• Composite number → its smallest prime factor (one operation)
• Prime number → stays the same (operation has no effect)

2. Processing Array from Left to Right

Pitfall: Attempting to process the array from left to right, trying to increase smaller elements to match larger ones.

Why it's wrong: The operation can only reduce numbers (or keep them the same for primes), never increase them. Processing left to right would lead to incorrect decisions about which elements need modification.

Solution: Always process from right to left. This ensures that when you reach position i, you already know the final value of nums[i+1], allowing you to make the correct decision about whether to reduce nums[i].

3. Memory Limit Issues with Preprocessing

Pitfall: Creating the smallest_prime_factor array with a fixed size of 10^6 + 1 can cause memory issues or be inefficient when the actual numbers in the input are much smaller.

Solution: Optimize the preprocessing based on the actual maximum value in the input:

def minOperations(self, nums: List[int]) -> int:
    max_val = max(nums)
  
    # Only compute up to what we need
    spf = [0] * (max_val + 1)
    for i in range(2, max_val + 1):
        if spf[i] == 0:
            for j in range(i, max_val + 1, i):
                if spf[j] == 0:
                    spf[j] = i
  
    # Rest of the algorithm...

4. Not Handling Edge Cases

Pitfall: Forgetting to handle special cases like:

• Arrays with single element (already non-decreasing)
• Arrays with all prime numbers
• Numbers less than 2 in the array

Solution: Add proper edge case handling:

def minOperations(self, nums: List[int]) -> int:
    if len(nums) <= 1:
        return 0
  
    # For numbers < 2, handle separately
    # 1 has no proper divisors, so it stays 1
    # 0 is not a natural number (problem states natural numbers)
  
    operation_count = 0
    for i in range(len(nums) - 2, -1, -1):
        if nums[i] > nums[i + 1]:
            if nums[i] < 2:  # Cannot be reduced
                return -1
            nums[i] = smallest_prime_factor[nums[i]]
            if nums[i] > nums[i + 1]:
                return -1
            operation_count += 1
  
    return operation_count

5. Misunderstanding "Greatest Proper Divisor"

Pitfall: Confusing greatest proper divisor with greatest common divisor (GCD) or thinking it's the number itself divided by 2.

Why it's wrong: The greatest proper divisor is the largest divisor that's strictly less than the number itself. For 12, it's 6 (not 4 or 2). The key insight is that dividing by the greatest proper divisor gives the smallest prime factor.

Solution: Use the mathematical property directly: for any composite number n, n / (greatest proper divisor) = smallest prime factor. This is why the preprocessing computes smallest prime factors rather than trying to find greatest proper divisors directly.