We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Division Operations to Make Array Non Decreasing

Difficulty: Medium

Problem Description

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

Key Insights

  • The greatest proper divisor of a number can be found by checking its divisors up to its square root.
  • For a number to be non-decreasing after operations, each number should be able to be reduced to at least the value of the previous number in the array.
  • If an operation cannot reduce a number sufficiently, it indicates that the array cannot be made non-decreasing.

Space and Time Complexity

Time Complexity: O(n * sqrt(m)), where n is the length of the array and m is the maximum value in the array.
Space Complexity: O(1), as we are using a constant amount of space.

Solution

To solve this problem, we can iterate through the array from the last element to the first. For each element, we check if it is already less than or equal to the next element. If not, we compute how many operations are needed to reduce it to a proper divisor that is less than or equal to the next element. This can be done by finding the greatest proper divisor of the current element. We will keep a count of operations needed and return this count if the array can be made non-decreasing, otherwise return -1 if it's impossible.

Code Solutions

def min_operations(nums):
    n = len(nums)
    operations = 0
    
    for i in range(n - 2, -1, -1):
        while nums[i] > nums[i + 1]:
            # Find the greatest proper divisor of nums[i]
            gpd = -1
            for j in range(1, int(nums[i]**0.5) + 1):
                if nums[i] % j == 0:
                    if j < nums[i]:
                        gpd = max(gpd, j)
                    if nums[i] // j < nums[i]:
                        gpd = max(gpd, nums[i] // j)

            if gpd == -1:
                return -1
            
            nums[i] //= gpd
            operations += 1
            
    return operations
← Back to All Questions