Minimum Division Operations to Make Array Non Decreasing

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.

Examples

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 <= 10^5
• 1 <= nums[i] <= 10^6

Solution

Method 1 – Greedy Backward Division

Intuition

To make the array non-decreasing, we need to ensure every element is less than or equal to the next. We process from right to left, dividing elements by their greatest proper divisor only when necessary. If at any point we cannot make an element small enough, it's impossible.

Approach

1. Start from the second last element and move left.
2. For each element, if it is greater than the next, repeatedly divide it by its greatest proper divisor until it becomes less than or equal to the next element.
3. Count each division as an operation.
4. If an element becomes 1 and is still greater than the next, return -1.
5. Return the total number of operations.

Code

C++

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int ans = 0;
        for (int i = nums.size() - 2; i >= 0; --i) {
            int cur = nums[i];
            int nxt = nums[i+1];
            int ops = 0;
            while (cur > nxt) {
                if (cur == 1) return -1;
                int div = cur / 2;
                for (int d = 2; d * d <= cur; ++d) {
                    if (cur % d == 0) div = max(div, cur / d);
                }
                cur = div;
                ++ops;
            }
            ans += ops;
            nums[i] = cur;
        }
        return ans;
    }
};

Go

func minOperations(nums []int) int {
    ans := 0
    for i := len(nums) - 2; i >= 0; i-- {
        cur := nums[i]
        nxt := nums[i+1]
        ops := 0
        for cur > nxt {
            if cur == 1 {
                return -1
            }
            div := cur / 2
            for d := 2; d*d <= cur; d++ {
                if cur%d == 0 && cur/d > div {
                    div = cur / d
                }
            }
            cur = div
            ops++
        }
        ans += ops
        nums[i] = cur
    }
    return ans
}

Java

class Solution {
    public int minOperations(int[] nums) {
        int ans = 0;
        for (int i = nums.length - 2; i >= 0; i--) {
            int cur = nums[i];
            int nxt = nums[i+1];
            int ops = 0;
            while (cur > nxt) {
                if (cur == 1) return -1;
                int div = cur / 2;
                for (int d = 2; d * d <= cur; d++) {
                    if (cur % d == 0) div = Math.max(div, cur / d);
                }
                cur = div;
                ops++;
            }
            ans += ops;
            nums[i] = cur;
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun minOperations(nums: IntArray): Int {
        var ans = 0
        for (i in nums.size - 2 downTo 0) {
            var cur = nums[i]
            val nxt = nums[i+1]
            var ops = 0
            while (cur > nxt) {
                if (cur == 1) return -1
                var div = cur / 2
                for (d in 2..Math.sqrt(cur.toDouble()).toInt()) {
                    if (cur % d == 0) div = maxOf(div, cur / d)
                }
                cur = div
                ops++
            }
            ans += ops
            nums[i] = cur
        }
        return ans
    }
}

Python

def min_operations(nums: list[int]) -> int:
    ans = 0
    for i in range(len(nums) - 2, -1, -1):
        cur = nums[i]
        nxt = nums[i+1]
        ops = 0
        while cur > nxt:
            if cur == 1:
                return -1
            div = cur // 2
            for d in range(2, int(cur ** 0.5) + 1):
                if cur % d == 0:
                    div = max(div, cur // d)
            cur = div
            ops += 1
        ans += ops
        nums[i] = cur
    return ans

Rust

impl Solution {
    pub fn min_operations(nums: &mut Vec<i32>) -> i32 {
        let mut ans = 0;
        for i in (0..nums.len()-1).rev() {
            let mut cur = nums[i];
            let nxt = nums[i+1];
            let mut ops = 0;
            while cur > nxt {
                if cur == 1 { return -1; }
                let mut div = cur / 2;
                let mut d = 2;
                while d * d <= cur {
                    if cur % d == 0 {
                        div = div.max(cur / d);
                    }
                    d += 1;
                }
                cur = div;
                ops += 1;
            }
            ans += ops;
            nums[i] = cur;
        }
        ans
    }
}

TypeScript

class Solution {
    minOperations(nums: number[]): number {
        let ans = 0;
        for (let i = nums.length - 2; i >= 0; i--) {
            let cur = nums[i];
            const nxt = nums[i+1];
            let ops = 0;
            while (cur > nxt) {
                if (cur === 1) return -1;
                let div = Math.floor(cur / 2);
                for (let d = 2; d * d <= cur; d++) {
                    if (cur % d === 0) div = Math.max(div, Math.floor(cur / d));
                }
                cur = div;
                ops++;
            }
            ans += ops;
            nums[i] = cur;
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n * sqrt(m)), where n is the length of nums and m is the maximum value in nums. For each element, we may need to check all divisors up to sqrt(m).
• 🧺 Space complexity: O(1), only a few variables are used for tracking the answer.