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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Division Operations to Make Array Non Decreasing

Number: 3607

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an integer array nums, you may perform an operation any number of times. In each operation, you choose one element and divide it by its greatest proper divisor (i.e. any positive divisor strictly less than the number; note that for primes the only proper divisor is 1 so applying the operation won’t change the number). The goal is to achieve an array that is non-decreasing (each element is less than or equal to the next). Return the minimum number of operations required, or -1 if it is not possible.

Key Insights

  • Only composite numbers can be reduced since dividing a prime by 1 does not change it.
  • The transformation on any number is deterministic: a composite number x will become x / (x / smallestPrimeFactor(x)) = smallestPrimeFactor(x) in one operation.
  • Process the array from right-to-left. The rightmost element sets the allowed bound and, moving left, each element must be reduced until it is no greater than the current bound.
  • If an element is prime (or equals 1) and still greater than the allowed bound, then it can never be reduced and the answer is -1.
  • Precomputing smallest prime factors (spf) up to the maximum value in nums allows O(1) transformation per operation.

Space and Time Complexity

Time Complexity: O(n log(max(nums)) + max(nums))
• O(max(nums)) for computing the SPF sieve, and
• O(n) iterations (each with a few constant time operations).
Space Complexity: O(max(nums)) for the SPF array.

Solution

We use a greedy approach processing the array from right-to-left. Initialize the allowed bound as the rightmost element’s value. For each element from the end moving left, if the element is greater than the allowed bound, repeatedly apply the operation (divide by its greatest proper divisor, which is computed using its smallest prime factor) until the element is less than or equal to the bound. If an element cannot be reduced (i.e. it is prime or equals 1) and still remains greater than the bound, return -1. Otherwise, update the allowed bound to the new value of the current element and continue. The cumulative operation count is the answer.

Data structures used include an array for smallest prime factors computed via a sieve. The algorithm leverages greedy processing, number theory (to obtain the greatest proper divisor quickly), and simulation of the given transformation.

Code Solutions

# Function to compute smallest prime factors up to n using a sieve approach.
def compute_spf(n):
    spf = list(range(n+1))
    for i in range(2, int(n**0.5)+1):
        if spf[i] == i:  # i is prime
            for j in range(i*i, n+1, i):
                if spf[j] == j:
                    spf[j] = i
    return spf

def minDivisionOperations(nums):
    # Precompute SPF (smallest prime factor) up to max(nums)
    max_val = max(nums)
    spf = compute_spf(max_val)
    operations = 0
    n = len(nums)
    # Set allowed bound to the last element in the array.
    allowed = nums[-1]
    
    # Process the array from right-to-left.
    for i in range(n-2, -1, -1):
        # While current element is greater than allowed bound.
        while nums[i] > allowed:
            # If the number is 1 or a prime (operation would be ineffective), return -1.
            if nums[i] == 1 or spf[nums[i]] == nums[i]:
                return -1
            # The greatest proper divisor of nums[i] is nums[i] / (nums[i] / spf[nums[i]]) which equals spf[nums[i]].
            # So update nums[i] to its smallest prime factor.
            nums[i] = spf[nums[i]]
            operations += 1
        # Update the allowed bound to maintain non-decreasing order.
        allowed = nums[i]
    return operations

# Example usage:
print(minDivisionOperations([25, 7]))  # Expected output: 1
print(minDivisionOperations([7, 7, 6]))  # Expected output: -1
print(minDivisionOperations([1, 1, 1, 1]))  # Expected output: 0
← Back to All Questions