Watch 5 video solutions for Minimum Division Operations to Make Array Non Decreasing, a medium level problem involving Array, Math, Greedy. This walkthrough by CodeFod has 716 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |