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 don’t get it!

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 by performing a series of operations. The catch? You can only divide elements by their divisors (greater than 1) to achieve this. If you can’t make the array non-decreasing, you’ll have to throw in the towel and return -1.

Imagine you’re at a party, and everyone is trying to outdo each other with their dance moves. If one person suddenly starts doing the worm while everyone else is doing the cha-cha, it’s going to be a disaster! Your job is to ensure that everyone is in sync, or at least as close as possible.

Code Solution

class Solution {
  public int minOperations(int[] nums) {
    int ans = 0;

    for (int i = nums.length - 2; i >= 0; --i)
      if (nums[i] > nums[i + 1]) {
        final int minDivisor = getMinDivisor(nums[i]);
        if (minDivisor > nums[i + 1])
          return -1;
        nums[i] = minDivisor;
        ++ans;
      }

    return ans;
  }

  private int getMinDivisor(int num) {
    for (int divisor = 2; divisor <= Math.sqrt(num); ++divisor)
      if (num % divisor == 0)
        return divisor;
    return num;
  }
}
    

Approach Explanation

The approach here is quite straightforward. 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 make a change. We find the smallest divisor of that element and check if it can be used to make the array non-decreasing. If it can’t, we return -1. Otherwise, we update the element and count the operation.

Time and Space Complexity

Time Complexity

O(n * √m), where n is the number of elements in the array and m is the maximum value in the array. This is because for each element, we may need to check up to √m for its divisors.

Space Complexity

O(1), as we are using a constant amount of space regardless of the input size.

Real-World Example

Let’s say you’re organizing a dance competition. Each contestant has a score, and you want to ensure that the scores are in non-decreasing order. If one contestant scores higher than the next, you can’t just let it slide! You might have to adjust their scores (divide them by their divisors) to maintain the order. If a contestant’s score is so high that it can’t be adjusted to fit, you might have to disqualify them (return -1).