Skip to main content
Talentd

Minimum Division Operations to Make Array Non Decreasing - Solution & Explanation

MediumArrayMathGreedyNumber Theory15 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

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 <= 105
  • 1 <= nums[i] <= 106

Approach Overview

Problem 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 1: Approach 1: Greedy Approach with Stack

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time complexity: O(n * sqrt(max(nums[i]))) due to the divisor calculation for each element.
Space complexity: O(n) for the stack usage.

Try this approach in the editor →

Approach 2: Approach 2: Backtracking Approach

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.

Code

C++Java

C++

Java

Complexity

Time complexity: Potentially exponential, especially for lengthy arrays with large elements.
Space complexity: O(n) due to recursion and storage requirements.

Try this approach in the editor →

Approach 3: Preprocessing + Greedy

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Greedy Approach with Stack

Time complexity: O(n * sqrt(max(nums[i]))) due to the divisor calculation for each element.
Space complexity: O(n) for the stack usage.

Approach 2: Backtracking Approach

Time complexity: Potentially exponential, especially for lengthy arrays with large elements.
Space complexity: O(n) due to recursion and storage requirements.

Preprocessing + Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with StackO(n log V)O(n)Best general solution for large arrays where elements must be adjusted minimally
BacktrackingExponentialO(n)Useful for understanding all possible division paths or validating small inputs

Video Solution

Leetcode Weekly Contest 420 | 3326. Minimum Division Operations to Make Array Non Decreasing CodeFod • CodeFod • 733 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Minimum Division Operations to Make Array Non Decreasing easy or hard?
The problem is rated Medium on LeetCode with an acceptance rate around 29%. The difficulty comes from recognizing the greedy invariant and understanding how divisor reductions interact with the non‑decreasing constraint.
Minimum Division Operations to Make Array Non Decreasing Python/Java solution
Most implementations follow the same greedy idea. Traverse the array from right to left, compare each value with the next allowed value, and perform divisions when needed. This approach can be implemented in Python, JavaScript, Java, or C++ with roughly O(n log V) complexity.
How to solve Minimum Division Operations to Make Array Non Decreasing in O(n)?
A near‑linear strategy processes the array from right to left and keeps the maximum allowed value for the current position. When an element exceeds this bound, divide it by appropriate divisors until it becomes valid. Because each operation significantly reduces the number, the practical complexity behaves close to O(n) for typical constraints.
What is the best approach for Minimum Division Operations to Make Array Non Decreasing?
The greedy right‑to‑left reduction approach is the most efficient. Iterate from the end of the array and ensure each element is less than or equal to the next valid value. If it is larger, repeatedly divide it using valid divisors until the constraint holds. This method minimizes operations locally and runs in about O(n log V) time.
Is Minimum Division Operations to Make Array Non Decreasing asked at Google/Amazon/Meta?
Problems combining greedy logic with number‑theory style reductions appear in interviews at companies like Google, Amazon, and Meta. Variants often test the ability to enforce ordering constraints in arrays while minimizing operations.
What data structure is used in Minimum Division Operations to Make Array Non Decreasing?
The common implementation uses a stack or a running bound variable while iterating from right to left. The stack stores validated elements and helps maintain the maximum allowed value for the previous index. The core logic relies on array traversal and divisor calculations.
What is the time complexity of Minimum Division Operations to Make Array Non Decreasing?
The optimal greedy solution runs in O(n log V) time where n is the array length and V is the maximum element value. Each element may be reduced multiple times, but division quickly shrinks numbers. Space complexity is O(n) if a stack is used, or O(1) if only a running bound is tracked.

Ready to solve this problem?

Practice Minimum Division Operations to Make Array Non Decreasing with our built-in code editor and test cases.

Practice on FleetCode
Previous

Smallest Value After Replacing With Sum of Prime Factors