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] <= 106In #3326 Minimum Division Operations to Make Array Non Decreasing, the goal is to transform the array so that it becomes non‑decreasing using the minimum number of division operations. The key observation is that dividing a number by its greatest proper divisor reduces it to its smallest prime factor. This property allows us to reason about how much an element can shrink with a single operation.
A common greedy strategy is to process the array from right to left. For each element, compare it with the next element. If the current value is already less than or equal to the next one, no action is needed. Otherwise, we attempt to reduce it using the allowed division operation so that it does not exceed the next value. If the reduced value is still larger than the next element, the configuration becomes impossible.
Efficient implementations often rely on number theory techniques such as precomputing smallest prime factors to quickly determine the result of each division. This leads to near-linear traversal of the array.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy traversal with smallest prime factor preprocessing | O(n + M log log M) | O(M) |
| Greedy traversal with on-demand factor computation | O(n log M) | O(1) |
Striver
Use these hints if you're stuck. Try solving on your own first.
Iterate backward from the last index.
Each number can be divided by its largest proper divisor to yield its smallest prime divisor.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Precomputing the smallest prime factor (SPF) for numbers using a sieve technique is a common optimization. It allows constant-time lookup for the reduced value after a division operation, significantly speeding up the greedy traversal.
Yes, this type of problem appears in technical interviews because it combines greedy reasoning with number theory insights. It tests a candidate's ability to recognize mathematical properties and apply them efficiently during array traversal.
The optimal approach uses a greedy strategy by scanning the array from right to left. When an element is larger than the next element, it is reduced using the allowed division operation so it becomes small enough to maintain the non-decreasing order. Number theory observations about smallest prime factors help make this process efficient.
A greedy approach works because each element only needs to be adjusted relative to the element on its right. By fixing violations from right to left, we ensure previously processed elements already satisfy the required ordering, minimizing unnecessary operations.