3326. Minimum Division Operations to Make Array Non Decreasing
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
. 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
Solutions
Solution 1: Preprocessing + Greedy
According to the problem description,
If an integer $x$ is a prime number, then its largest proper divisor is $1$, so $x / 1 = x$, meaning $x$ cannot be divided further.
If an integer $x$ is not a prime number, we assume the largest proper divisor of $x$ is $y$, then $x / y$ must be a prime number. Therefore, we find the smallest prime factor $\textit{lpf}[x]$ such that $x \bmod \textit{lpf}[x] = 0$, making $x$ become $\textit{lpf}[x]$, at which point it cannot be divided further.
Thus, we can preprocess the smallest prime factor for each integer from $1$ to $10^6$. Then, we traverse the array from right to left. If the current element is greater than the next element, we change the current element to its smallest prime factor. If after changing the current element to its smallest prime factor it is still greater than the next element, it means the array cannot be made non-decreasing, and we return $-1$. Otherwise, we increment the operation count by one. Continue traversing until the entire array is processed.
The time complexity for preprocessing is $O(M \times \log \log M)$, where $M = 10^6$. The time complexity for traversing the array is $O(n)$, where $n$ is the length of the array. The space complexity is $O(M)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|