Minimum Division Operations to Make Array Non Decreasing
MedPrompt
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 <= 1051 <= nums[i] <= 106
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- State Representation: Each unique configuration of the
numsarray 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.
- Initialize a queue and add the initial state
(initial_nums, 0). A state is a pair of the array and the number of operations. - Use a
Setto store visited array configurations to avoid cycles and redundant work. - While the queue is not empty:
a. Dequeue
(current_array, ops). b. Ifcurrent_arrayis non-decreasing, returnopsas it's the minimum. c. For each elementnums[i]incurrent_array: i. Check ifnums[i]is composite. If so, it can be operated on. ii. Calculate the new valuenew_valby applying the operation. iii. Create anext_arraywith this change. iv. Ifnext_arrayhas not been visited, add it to the visited set and enqueue(next_array, ops + 1).
- Initialize a queue and add the initial state
Walkthrough
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.
Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.