#3326

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Minimum Division Operations to Make Array Non Decreasing

Determine the minimum number of division operations to make an array non-decreasing using a greedy and invariant-based strategy.

array math greedy number theory

Problem Statement

Given an integer array nums, you can perform any number of operations where you select one element and divide it by its greatest proper divisor. A proper divisor of a number x is any positive integer less than x that divides x evenly.

Your task is to find the minimum number of such division operations needed to transform nums into a non-decreasing array. If it is impossible to achieve a non-decreasing sequence, return -1.

Examples

Example 1

Input: nums = [25,7]

Output: 1

Using a single operation, 25 gets divided by 5 and nums becomes [5, 7] .

Example 2

Input: nums = [7,7,6]

Output: -1

Example details omitted.

Example 3

Input: nums = [1,1,1,1]

Output: 0

Example details omitted.

Constraints

1 <= nums.length <= 105
1 <= nums[i] <= 106

Solution Approach

Iterate Backwards with Greedy Division

Start from the end of the array and move left, ensuring each element is less than or equal to the next. If an element is larger, divide it by its largest proper divisor repeatedly until the invariant holds.

Count Operations Efficiently

Maintain a counter for each division performed. Since each division reduces the number, ensure no unnecessary divisions are applied beyond what is needed to satisfy the non-decreasing condition.

Check for Impossible Cases

If an element becomes 1 and is still larger than its next neighbor, the sequence cannot be fixed. Immediately return -1 to handle these failure cases efficiently.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of division operations applied to each element, potentially O(n log m) where n is array length and m is the maximum element. Space complexity is O(1) extra beyond the input array.

What Interviewers Usually Probe

Are you considering the largest proper divisor in each step?
Can you explain why iterating backward simplifies maintaining the invariant?
How do you handle elements that cannot be reduced further but still violate the non-decreasing property?

Common Pitfalls or Variants

Common pitfalls

Dividing elements unnecessarily instead of only when they violate the non-decreasing condition.
Iterating forward instead of backward, which complicates invariant validation.
Forgetting to return -1 when an element cannot be reduced enough to satisfy the sequence.

Follow-up variants

Compute minimum multiplication operations to make an array non-increasing.
Allow division by any proper divisor rather than only the greatest and track minimum operations.
Apply similar greedy operations on 2D arrays row by row while maintaining non-decreasing order.

FAQ

What is the key greedy strategy for this problem?

Always divide elements from right to left using the largest proper divisor to maintain the non-decreasing invariant.

How do I know if the array cannot be fixed?

If an element reaches 1 and is still larger than the next element, return -1 because no further valid operations exist.

Can I divide by divisors other than the greatest proper divisor?

The problem specifies using the greatest proper divisor, as smaller divisors may require more operations and break the greedy minimization.

Does this solution work efficiently for large arrays?

Yes, iterating backward and applying divisions only when necessary ensures the algorithm scales with array length and maximum element size.

Is there a variation involving multiplication instead of division?

Yes, a similar greedy approach can be applied in reverse to make arrays non-increasing using multiplication operations.

terminal

Solution

Solution 1: Preprocessing + Greedy

According to the problem description,

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

mx = 10**6 + 1
lpf = [0] * (mx + 1)
for i in range(2, mx + 1):
    if lpf[i] == 0:
        for j in range(i, mx + 1, i):
            if lpf[j] == 0:
                lpf[j] = i


class Solution:
    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]]
                if nums[i] > nums[i + 1]:
                    return -1
                ans += 1
        return ans

Continue Practicing

#3605 minimum stability factor of array #3012 minimize length of array using operations #2818 apply operations to maximize score