Minimum Division Operations to Make Array Non-Decreasing

Problem Description

Ah, the classic dilemma of making an array non-decreasing! It’s like trying to convince your friend to stop telling embarrassing stories about you at parties. You know it’s for their own good, but they just won’t listen!

In this problem, you are given an array of integers, and your mission, should you choose to accept it, is to make this array non-decreasing. But wait! There’s a catch! You can only reduce the elements of the array by dividing them by their divisors. So, if you thought you could just slap a few numbers around, think again!

Imagine you have a list of your friends’ heights, and you want to arrange them in a line from shortest to tallest. But instead of just asking them to stand on their tiptoes, you can only make them shorter by using a magic shrinking potion (a.k.a. divisors). If a friend is taller than the one next to them, you need to find a way to shrink them down to size.

Your task is to find the minimum number of operations required to achieve this. If it’s impossible, you’ll have to throw your hands up in despair and return -1.

Code Solution


class Solution:
    def minOperations(self, nums: list[int]) -> int:
        ans = 0

        for i in range(len(nums) - 2, -1, -1):
            if nums[i] > nums[i + 1]:
                minDivisor = self._getMinDivisor(nums[i])
                if minDivisor > nums[i + 1]:
                    return -1
                nums[i] = minDivisor
                ans += 1

        return ans

    def _getMinDivisor(self, num: int) -> int:
        for divisor in range(2, math.isqrt(num) + 1):
            if num % divisor == 0:
                return divisor
        return num

Approach Explanation

The approach here is quite straightforward, yet clever! We start from the end of the array and work our way to the front. If we find an element that is greater than the next one, we need to reduce it. To do this, we find the smallest divisor of that element. If that divisor is still greater than the next element, we throw in the towel and return -1. Otherwise, we replace the current element with its smallest divisor and count this as one operation.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n * √m)
Space Complexity	O(1)

Real-World Example

Let’s say you’re organizing a basketball game, and you have a list of players with their heights. You want to make sure that no player is taller than the one next to them. If one player is 6 feet tall and the next is 5 feet, you can’t just ask the 6-foot player to shrink down to 5 feet. Instead, you can find a way to reduce their height using some magical divisor. If you can’t find a suitable divisor, you might as well call it a day and cancel the game!