You are given an integer array nums.
Any positive divisor of a natural number x that is strictly less than x is called a proper divisor of x. For example, 2 is a proper divisor of 4, while 6 is not a proper divisor of 6.
You are allowed to perform an operation any number of times on nums, where in each operation you select any one element from nums and divide it by its greatest proper divisor.
Return the minimum number of operations required to make the array non-decreasing.
If it is not possible to make the array non-decreasing using any number of operations, return -1.
Example 1:
Input: nums = [25,7]
Output: 1
Explanation:
Using a single operation, 25 gets divided by 5 and nums becomes [5, 7].
Example 2:
Input: nums = [7,7,6]
Output: -1
Example 3:
Input: nums = [1,1,1,1]
Output: 0
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 106Problem Overview: You are given an integer array and can repeatedly divide an element by one of its divisors. The goal is to perform the minimum number of division operations so the array becomes non‑decreasing. If it cannot be achieved, return -1.
Approach 1: Greedy Approach with Stack (O(n log V) time, O(n) space)
The array must satisfy nums[i] ≤ nums[i+1]. Work from right to left and maintain a stack (or effectively track the allowed upper bound for the current element). If the current number is already ≤ the next valid value, push it and continue. If it is larger, repeatedly divide it by one of its valid divisors to reduce it. The greedy insight: always reduce the number as little as necessary so it becomes ≤ the next element. Using number‑theory operations (such as reducing by a smallest prime factor or divisor) ensures the value decreases quickly while minimizing operations. The stack keeps previously validated elements so you always know the current upper limit. Each element may be reduced a few times but values shrink quickly, giving roughly O(n log V) time where V is the max value.
This approach fits well with problems combining array traversal and greedy decisions. You locally enforce the ordering constraint and never revisit earlier indices.
Approach 2: Backtracking Approach (Exponential worst case, O(n) recursion space)
Backtracking explores all possible division choices for each element. For a given index, generate all values reachable by dividing the number with its divisors, then recursively check if the remaining array can be made non‑decreasing. Track the minimum operations among valid paths. While this guarantees the optimal answer, the branching factor can grow quickly because a number may have many divisors and multiple sequences of divisions. The worst‑case time becomes exponential, making it impractical for large inputs.
This method mainly demonstrates the brute force search space and helps reason about why greedy pruning works. The recursion explores combinations driven by number theory properties of divisors.
Recommended for interviews: The greedy right‑to‑left reduction is the expected solution. It enforces the non‑decreasing constraint while minimizing operations locally. Backtracking shows the full search space, but interviewers typically look for the greedy insight that shrinking each violating element to the largest valid value keeps the operation count minimal and runs efficiently.
This approach leverages a greedy method using a stack to maintain the non-decreasing property of the array. The goal is to use as few operations as possible to correct any decrease in the sequence.
We traverse the array from left to right, using a stack to track the current non-decreasing sequence. If the current number in the array is smaller than the top of the stack, it indicates a decrease in the sequence. We then repeatedly divide the number at the top of the stack by its greatest proper divisor until it is less than or equal to the current number, counting each operation. This ensures we only perform operations when necessary to maintain the non-decreasing order.
Finally, we check whether the sequence after the operations is non-decreasing and return the total number of operations. If the sequence cannot be made non-decreasing, we return -1.
The Python solution employs a helper function to find the greatest proper divisor of a number. We iterate through the nums list, and for each number, we ensure the stack remains non-decreasing by popping elements when necessary and replacing them after dividing by their divisors. The total number of operations needed or -1 if unsuccessful is then returned.
Python
JavaScript
Time complexity: O(n * sqrt(max(nums[i]))) due to the divisor calculation for each element.
Space complexity: O(n) for the stack usage.
This approach involves a recursive backtracking method where each element is iteratively tested with all possible division operations, exploring different combinations to find the minimal operation count that results in a non-decreasing array.
This is more of an exploratory approach, which attempts all possible divides at each step to find the minimally required operations, but is left here for completeness.
The C++ solution exemplifies a backtracking approach, testing various divisions recursively to achieve a non-decreasing sequence, recording minimal operations. The helper function iteratively checks each number's divisors recursively until a valid sequence emerges.
Time complexity: Potentially exponential, especially for lengthy arrays with large elements.
Space complexity: O(n) due to recursion and storage requirements.
According to the problem description,
If an integer x is a prime number, then its largest proper divisor is 1, so x / 1 = x, meaning x cannot be divided further.
If an integer x is not a prime number, we assume the largest proper divisor of x is y, then x / y must be a prime number. Therefore, we find the smallest prime factor lpf[x] such that x bmod lpf[x] = 0, making x become lpf[x], at which point it cannot be divided further.
Thus, we can preprocess the smallest prime factor for each integer from 1 to 10^6. Then, we traverse the array from right to left. If the current element is greater than the next element, we change the current element to its smallest prime factor. If after changing the current element to its smallest prime factor it is still greater than the next element, it means the array cannot be made non-decreasing, and we return -1. Otherwise, we increment the operation count by one. Continue traversing until the entire array is processed.
The time complexity for preprocessing is O(M times log log M), where M = 10^6. The time complexity for traversing the array is O(n), where n is the length of the array. The space complexity is O(M).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Greedy Approach with Stack | Time complexity: O(n * sqrt(max(nums[i]))) due to the divisor calculation for each element. |
| Approach 2: Backtracking Approach | Time complexity: Potentially exponential, especially for lengthy arrays with large elements. |
| Preprocessing + Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Stack | O(n log V) | O(n) | Best general solution for large arrays where elements must be adjusted minimally |
| Backtracking | Exponential | O(n) | Useful for understanding all possible division paths or validating small inputs |
Leetcode Weekly Contest 420 | 3326. Minimum Division Operations to Make Array Non Decreasing CodeFod • CodeFod • 716 views views
Watch 4 more video solutions →Practice Minimum Division Operations to Make Array Non Decreasing with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor