Minimum Division Operations to Make Array Non Decreasing solution and explanation
Google
4 more videos on this problem
Leetcode Weekly Contest 420 | 3326. Minimum Division Operations to Make Array Non Decreasing CodeFodCodeFod · 15:35 · 733 views
3326. Minimum Division Operations to Make Array Non Decreasing (Leetcode Medium)Programming Live with Larry · 14:40 · 408 views
3326. Minimum Division Operations to Make Array Non Decreasing | Leetcode Weekly contest 420Dev · 14:57 · 288 views
Leetcode | Weekly Contest 420 | Minimum Division Operations to Make Array Non Decreasing | SolutionCode Wanderer · 14:05 · 76 views
3326. Minimum Division Operations to Make Array Non Decreasing || #Leetcode Today Contest Solution||Jignesh · 0:55 · 29 views
The problem
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] <= 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.
def minOperations(nums):
def greatest_proper_divisor(x):
import math
for i in range(int(math.sqrt(x)), 0, -1):
if x % i == 0 and i != x:
return x // i
return 1
operations = 0
stack = []
for num in nums:
while stack and stack[-1] > num:
top = stack.pop()
while top >= num:
top = greatest_proper_divisor(top)
operations += 1
stack.append(top)
stack.append(num)
return operations if stack == sorted(stack) else -1function minOperations(nums) {
const greatestProperDivisor = (x) => {
for (let i = Math.floor(Math.sqrt(x)); i > 0; i--) {
if (x % i === 0 && i !== x) {
return x / i;
}
}
return 1;
};
let operations = 0;
let stack = [];
for (let num of nums) {
while (stack.length && stack[stack.length - 1] > num) {
let top = stack.pop();
while (top >= num) {
top = greatestProperDivisor(top);
operations++;
}
stack.push(top);
}
stack.push(num);
}
return isNonDecreasing(stack) ? operations : -1;
function isNonDecreasing(arr) {
for (let i = 1; i < arr.length; i++) {
if (arr[i - 1] > arr[i]) return false;
}
return true;
}
}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.
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: 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.
import java.util.Arrays;
public class Solution {
public int greatestProperDivisor(int x) {
for (int i = (int)Math.sqrt(x); i > 0; --i) {
if (x % i == 0 && i != x) {
return x / i;
}
}
return 1;
}
public boolean isNonDecreasing(int[] nums) {
for (int i = 1; i < nums.length; i++) {
if (nums[i - 1] > nums[i]) {
return false;
}
}
return true;
}
public int helper(int[] nums, int index, int currentOps) {
if (index == nums.length) {
return isNonDecreasing(nums) ? currentOps : Integer.MAX_VALUE;
}
int num = nums[index];
int minOps = Integer.MAX_VALUE;
while (num > 0) {
nums[index] = num;
minOps = Math.min(minOps, helper(nums, index + 1, currentOps));
num = greatestProperDivisor(num);
currentOps++;
}
return minOps;
}
public int minOperations(int[] nums) {
if (isNonDecreasing(nums)) return 0;
int ops = helper(nums, 0, 0);
return ops == Integer.MAX_VALUE ? -1 : ops;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {25, 7};
System.out.println(sol.minOperations(nums));
}
}#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int greatestProperDivisor(int x) {
for (int i = sqrt(x); i > 0; --i){
if (x % i == 0 && i != x) {
return x / i;
}
}
return 1;
}
bool canBeNonDecreasing(vector<int>& nums) {
for (int i = 1; i < nums.size(); ++i) {
if (nums[i-1] > nums[i]) {
return false;
}
}
return true;
}
int helper(vector<int>& nums, int index, int currentOps) {
if (index == nums.size()) {
return canBeNonDecreasing(nums) ? currentOps : INT_MAX;
}
int num = nums[index];
int minOps = INT_MAX;
while(num > 0) {
nums[index] = num;
minOps = min(minOps, helper(nums, index + 1, currentOps));
num = greatestProperDivisor(num);
++currentOps;
}
return minOps;
}
int minOperations(vector<int>& nums) {
if (canBeNonDecreasing(nums)) return 0;
int ops = helper(nums, 0, 0);
return ops == INT_MAX ? -1 : ops;
}
int main() {
vector<int> nums = {25, 7};
cout << minOperations(nums) << endl;
return 0;
}The Java solution mirrors the C++ backtracking approach, attempting all possible divisor combinations recursively. The program checks whether the modified array achieves a non-decreasing state, returning the minimum count of operations found or -1.
Time complexity: Could be exponential in the worst-case scenario.
Space complexity: O(n), mainly due to recursion and backtracking stack requirements.
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).
const mx = 10 ** 6;
const lpf = Array(mx + 1).fill(0);
for (let i = 2; i <= mx; ++i) {
for (let j = i; j <= mx; j += i) {
if (lpf[j] === 0) {
lpf[j] = i;
}
}
}
function minOperations(nums: number[]): number {
let ans = 0;
for (let i = nums.length - 2; ~i; --i) {
if (nums[i] > nums[i + 1]) {
nums[i] = lpf[nums[i]];
if (nums[i] > nums[i + 1]) {
return -1;
}
++ans;
}
}
return ans;
}const mx int = 1e6
var lpf = [mx + 1]int{}
func init() {
for i := 2; i <= mx; i++ {
if lpf[i] == 0 {
for j := i; j <= mx; j += i {
if lpf[j] == 0 {
lpf[j] = i
}
}
}
}
}
func minOperations(nums []int) (ans int) {
for i := len(nums) - 2; i >= 0; i-- {
if nums[i] > nums[i+1] {
nums[i] = lpf[nums[i]]
if nums[i] > nums[i+1] {
return -1
}
ans++
}
}
return
}Complexity comparison
| 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: Could be exponential in the worst-case scenario. |
| Preprocessing + Greedy | – |
Complexity analysis
| 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 |
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.