# Minimum Division Operations to Make Array Non Decreasing
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-division-operations-to-make-array-non-decreasing)
Canonical: https://scaleengineer.com/dsa/problems/minimum-division-operations-to-make-array-non-decreasing
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Data structures:** Array
---
## 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`.

**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 <= 105`
* `1 <= nums[i] <= 106`

# Approaches
## Brute-Force Search using BFS
This approach models the problem as a shortest path search on a state-space graph. Each state represents a possible version of the `nums` array, and we explore possible operations layer by layer using Breadth-First Search (BFS). The first time we find an array that is non-decreasing, we have found the solution with the minimum number of operations. To find if a number can be changed (i.e., it's composite), we would need to factorize it on the fly.
**Time:** O(S * N * sqrt(M)), where S is the number of states, N is the array length, and M is the max value. The `sqrt(M)` factor comes from checking for primality/compositeness for each operation. The number of states S is prohibitively large. · **Space:** O(S * N), where S is the number of reachable states and N is the array length. In the worst case, S can be exponential.
**Pros:** Guaranteed to find the optimal solution if one exists.; Conceptually straightforward application of a standard graph algorithm.
**Cons:** Extremely high time complexity, making it infeasible for the given constraints.; Requires a large amount of memory to store the queue and the set of visited states.
### Explanation
The core idea is to treat every possible configuration of the `nums` array as a node in a vast graph. An operation that transforms one array configuration into another is a directed edge between the corresponding nodes. Since each operation has a cost of 1, the problem of finding the minimum number of operations is equivalent to finding the shortest path from the initial array configuration to any valid (non-decreasing) configuration. BFS is the standard algorithm for finding the shortest path in an unweighted graph. We start with the initial array and explore all arrays reachable in 1 operation, then all arrays reachable in 2 operations, and so on. A `visited` set is crucial to prevent re-processing the same array configuration, which would lead to infinite loops and redundant computations. However, the number of possible states is astronomically large, rendering this approach impractical.
### Algorithm
- **State Representation**: Each unique configuration of the `nums` array is a state in a graph.
- **Edges**: An edge exists from state A to state B if B can be reached from A by one operation.
- **Goal**: Find the shortest path from the initial state to any state where the array is non-decreasing.
- **Algorithm**: Use Breadth-First Search (BFS) to find this shortest path.
  1. Initialize a queue and add the initial state `(initial_nums, 0)`. A state is a pair of the array and the number of operations.
  2. Use a `Set` to store visited array configurations to avoid cycles and redundant work.
  3. While the queue is not empty:
     a. Dequeue `(current_array, ops)`.
     b. If `current_array` is non-decreasing, return `ops` as it's the minimum.
     c. For each element `nums[i]` in `current_array`:
        i. Check if `nums[i]` is composite. If so, it can be operated on.
        ii. Calculate the new value `new_val` by applying the operation.
        iii. Create a `next_array` with this change.
        iv. If `next_array` has not been visited, add it to the visited set and enqueue `(next_array, ops + 1)`.

## Greedy Approach with On-the-fly Factorization
A more feasible method is a greedy approach. We iterate from right to left, ensuring the non-decreasing property `nums[i] <= nums[i+1]` holds. When we encounter a violation (`nums[i] > nums[i+1]`), we must reduce `nums[i]`. The operation transforms a composite number `x` to its smallest prime factor `spf(x)`. A prime number cannot be changed. If `nums[i]` is composite, we apply the operation once. If the new value is still too large, or if `nums[i]` was prime to begin with, a solution is impossible. In this version of the approach, we calculate the `spf` for each number as needed using trial division.
**Time:** O(N * sqrt(M)), where N is the length of `nums` and M is the maximum possible value of an element. The main loop runs N times, and finding the smallest prime factor can take up to O(sqrt(M)) time. · **Space:** O(1) extra space, assuming the input array can be modified in-place.
**Pros:** Vastly more efficient than brute-force.; Correctly identifies the greedy nature of the problem.; Low space complexity.
**Cons:** The repeated on-the-fly calculation of smallest prime factors can be inefficient and may lead to a 'Time Limit Exceeded' verdict for large inputs.
### Explanation
This greedy strategy works because decisions made at index `i` do not invalidate the already-established property for indices greater than `i`. By processing from right to left, when we consider the pair `(nums[i], nums[i+1])`, the value of `nums[i+1]` has already been finalized to be as large as possible while satisfying `nums[i+1] <= nums[i+2]`. To satisfy `nums[i] <= nums[i+1]`, we must decrease `nums[i]` if it's larger. Since a composite number becomes prime (and thus unchangeable) after one operation, we have at most one chance to fix `nums[i]`. We perform the operation and check if the condition is now met. If not, it's impossible. The main bottleneck of this specific implementation is the factorization step.

Here is a code snippet for the helper function and the main logic:
```java
class Solution {
    private int getSmallestPrimeFactor(int n) {
        if (n <= 1) return n;
        if (n % 2 == 0) return 2;
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) {
                return i;
            }
        }
        return n; // n is prime
    }

    public int minimumOperations(int[] nums) {
        int n = nums.length;
        int operations = 0;
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] > nums[i+1]) {
                int currentNum = nums[i];
                int spf = getSmallestPrimeFactor(currentNum);
                if (spf == currentNum) { // currentNum is prime
                    return -1;
                }
                currentNum = spf;
                operations++;
                if (currentNum > nums[i+1]) {
                    return -1;
                }
                nums[i] = currentNum;
            }
        }
        return operations;
    }
}
```
### Algorithm
- **Greedy Choice**: Iterate the array from right to left (`i` from `n-2` down to `0`). For each `i`, ensure `nums[i] <= nums[i+1]`.
- **Modification**: If `nums[i] > nums[i+1]`, we must reduce `nums[i]`.
- **Operation**: The operation transforms a composite number `x` into its smallest prime factor (`spf(x)`). A prime number cannot be changed.
- **Algorithm Steps**:
  1. Initialize `total_operations = 0`.
  2. Loop `i` from `n-2` down to `0`.
  3. If `nums[i] > nums[i+1]`:
     a. Find the smallest prime factor of `nums[i]`, let's call it `spf_val`, using a helper function that performs trial division (checking divisibility up to `sqrt(nums[i])`).
     b. If `nums[i]` is prime (`spf_val == nums[i]`), it cannot be reduced. Return `-1`.
     c. `nums[i]` is composite. Apply the operation: `nums[i] = spf_val`. Increment `total_operations`.
     d. The new `nums[i]` is now prime. If it's still greater than `nums[i+1]`, it's impossible to satisfy the condition. Return `-1`.
  4. Return `total_operations`.

## Optimal Greedy Approach with Sieve Pre-computation
This is the most efficient approach. It builds upon the greedy strategy by significantly optimizing the most time-consuming part: finding the smallest prime factor. By pre-computing the SPF for all numbers up to the constraint maximum (`10^6`) using a Sieve of Eratosthenes variant, we can retrieve the SPF of any number in constant time. This makes the main loop, which iterates through the array from right to left, very fast.
**Time:** O(M log log M + N), where M is the maximum value and N is the array length. The sieve pre-computation takes O(M log log M), and the main loop takes O(N). · **Space:** O(M), where M is the maximum possible value of an element (`10^6`), for storing the `spf` array.
**Pros:** Optimal time complexity due to O(1) SPF lookups.; The greedy strategy is sound and correctly solves the problem.
**Cons:** Requires O(M) auxiliary space for the sieve array, which could be an issue in highly memory-constrained scenarios.
### Explanation
The overall strategy remains the same: a right-to-left greedy pass. The key improvement is the pre-computation step. A sieve algorithm can efficiently find the smallest prime factor for every number up to a limit `M`. This is done once. After this, the main logic can proceed, and whenever it needs the smallest prime factor of a number `x`, it can simply look it up in the pre-computed `spf` array at index `x`. This reduces the complexity of each step inside the main loop from `O(sqrt(M))` to `O(1)`, leading to a much better overall time complexity.

Here is a sample implementation:
```java
class Solution {
    private static final int MAX_VAL = 1000001;
    private static final int[] spf = new int[MAX_VAL];

    // Static initializer block to run the sieve once per class load
    static {
        for (int i = 0; i < MAX_VAL; i++) {
            spf[i] = i;
        }
        for (int i = 2; i * i < MAX_VAL; i++) {
            if (spf[i] == i) { // i is a prime number
                for (int j = i * i; j < MAX_VAL; j += i) {
                    if (spf[j] == j) { // if spf[j] is not set yet
                        spf[j] = i;
                    }
                }
            }
        }
    }

    public int minimumOperations(int[] nums) {
        int n = nums.length;
        int operations = 0;
        // We need to create a copy if we cannot modify the input, 
        // but problem context implies we can. Let's assume modification is allowed.
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] > nums[i+1]) {
                int currentNum = nums[i];
                // If currentNum is prime (and > 1), it cannot be reduced.
                if (spf[currentNum] == currentNum) { 
                    return -1;
                }
                // Perform one operation: num becomes its smallest prime factor.
                currentNum = spf[currentNum];
                operations++;
                // After one op, the number is prime. If it's still too large, impossible.
                if (currentNum > nums[i+1]) {
                    return -1;
                }
                nums[i] = currentNum;
            }
        }
        return operations;
    }
}
```
### Algorithm
- **Pre-computation**: Before processing the array, pre-compute the Smallest Prime Factor (SPF) for all numbers up to the maximum possible value (`10^6`) using a Sieve.
  1. Create an `spf` array of size `10^6 + 1`.
  2. Initialize `spf[i] = i`.
  3. Iterate `p` from 2. If `spf[p] == p`, `p` is prime. For all multiples `j` of `p`, set `spf[j] = p` if it's not already set.
- **Greedy Logic**: The core logic is the same as the previous greedy approach, but SPF lookups are now O(1).
  1. Initialize `total_operations = 0`.
  2. Loop `i` from `n-2` down to `0`.
  3. If `nums[i] > nums[i+1]`:
     a. Get `spf_val = spf[nums[i]]` in O(1) time.
     b. If `spf_val == nums[i]` (`nums[i]` is prime), return `-1`.
     c. `nums[i]` becomes `spf_val`. Increment `total_operations`.
     d. If the new `nums[i]` is still greater than `nums[i+1]`, return `-1`.
  4. Return `total_operations`.

# Solutions
### Java

```java
class Solution {
private
  static final int MX = (int)1 e6 + 1;
private
  static final int[] LPF = new int[MX + 1];
  static {
    for (int i = 2; i <= MX; ++i) {
      for (int j = i; j <= MX; j += i) {
        if (LPF[j] == 0) {
          LPF[j] = i;
        }
      }
    }
  }
public
  int minOperations(int[] nums) {
    int ans = 0;
    for (int i = nums.length - 2; i >= 0; i--) {
      if (nums[i] > nums[i + 1]) {
        nums[i] = LPF[nums[i]];
        if (nums[i] > nums[i + 1]) {
          return -1;
        }
        ans++;
      }
    }
    return ans;
  }
}

```

### Python

```python
mx = 10 ** 6 + 1 lpf = [ 0 ] * ( mx + 1 ) for i in range ( 2 , mx + 1 ): if lpf [ i ] == 0 : for j in range ( i , mx + 1 , i ): if lpf [ j ] == 0 : lpf [ j ] = i 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 ]: nums [ i ] = lpf [ nums [ i ]] if nums [ i ] > nums [ i + 1 ]: return - 1 ans += 1 return ans
```

### CPP

```cpp
const int MX = 1e6 ; int LPF [ MX + 1 ]; auto init = [] { for ( int i = 2 ; i <= MX ; i ++ ) { if ( LPF [ i ] == 0 ) { for ( int j = i ; j <= MX ; j += i ) { if ( LPF [ j ] == 0 ) { LPF [ j ] = i ; } } } } return 0 ; }(); class Solution { public: int minOperations ( vector < int >& nums ) { int ans = 0 ; for ( int i = nums . size () - 2 ; i >= 0 ; i -- ) { if ( nums [ i ] > nums [ i + 1 ]) { nums [ i ] = LPF [ nums [ i ]]; if ( nums [ i ] > nums [ i + 1 ]) { return - 1 ; } ans ++ ; } } return ans ; } };
```