You are given a 0-indexed integer array nums containing positive integers.
Your task is to minimize the length of nums by performing the following operations any number of times (including zero):
i and j from nums, such that nums[i] > 0 and nums[j] > 0.nums[i] % nums[j] at the end of nums.i and j from nums.Return an integer denoting the minimum length of nums after performing the operation any number of times.
Example 1:
Input: nums = [1,4,3,1] Output: 1 Explanation: One way to minimize the length of the array is as follows: Operation 1: Select indices 2 and 1, insert nums[2] % nums[1] at the end and it becomes [1,4,3,1,3], then delete elements at indices 2 and 1. nums becomes [1,1,3]. Operation 2: Select indices 1 and 2, insert nums[1] % nums[2] at the end and it becomes [1,1,3,1], then delete elements at indices 1 and 2. nums becomes [1,1]. Operation 3: Select indices 1 and 0, insert nums[1] % nums[0] at the end and it becomes [1,1,0], then delete elements at indices 1 and 0. nums becomes [0]. The length of nums cannot be reduced further. Hence, the answer is 1. It can be shown that 1 is the minimum achievable length.
Example 2:
Input: nums = [5,5,5,10,5] Output: 2 Explanation: One way to minimize the length of the array is as follows: Operation 1: Select indices 0 and 3, insert nums[0] % nums[3] at the end and it becomes [5,5,5,10,5,5], then delete elements at indices 0 and 3. nums becomes [5,5,5,5]. Operation 2: Select indices 2 and 3, insert nums[2] % nums[3] at the end and it becomes [5,5,5,5,0], then delete elements at indices 2 and 3. nums becomes [5,5,0]. Operation 3: Select indices 0 and 1, insert nums[0] % nums[1] at the end and it becomes [5,5,0,0], then delete elements at indices 0 and 1. nums becomes [0,0]. The length of nums cannot be reduced further. Hence, the answer is 2. It can be shown that 2 is the minimum achievable length.
Example 3:
Input: nums = [2,3,4] Output: 1 Explanation: One way to minimize the length of the array is as follows: Operation 1: Select indices 1 and 2, insert nums[1] % nums[2] at the end and it becomes [2,3,4,3], then delete elements at indices 1 and 2. nums becomes [2,3]. Operation 2: Select indices 1 and 0, insert nums[1] % nums[0] at the end and it becomes [2,3,1], then delete elements at indices 1 and 0. nums becomes [1]. The length of nums cannot be reduced further. Hence, the answer is 1. It can be shown that 1 is the minimum achievable length.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 109For #3012 Minimize Length of Array Using Operations, the key insight comes from observing how the operation interacts with the smallest element in the array. Since modulo-style reductions always produce values smaller than the larger operand, the minimum value plays a critical role in determining how much the array can shrink.
Start by identifying the minimum element in the array and counting its frequency. If there exists any number that is not divisible by this minimum, repeated operations can generate smaller remainders, eventually collapsing the array down to a single element. Otherwise, if all elements are multiples of the minimum value, the only effective reductions happen among the occurrences of that minimum itself.
This leads to a greedy observation: the final size depends largely on how many times the minimum element appears and how operations combine those values. By counting and reasoning about divisibility, the problem can be solved in linear time without simulation.
Time Complexity: O(n) for a single pass to compute the minimum and counts.
Space Complexity: O(1) since only a few variables are required.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy with Minimum Element Analysis | O(n) | O(1) |
| Naive Simulation of Operations | O(n^2) or worse | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
The problem can be solved by considering different cases.
Let the minimum value in <code>nums</code> be <code>x</code>; we can consider the following cases:
If <code>x</code> occurs once: The minimum length of <code>nums</code> achievable in this case is <code>1</code>, since every other value, <code>y</code>, can be paired with <code>x</code>, resulting in deleting <code>x</code> and <code>y</code>, and inserting <code>x % y == x</code>, since <code>x < y</code>. So, only <code>x</code> remains after the operations.
If there is a value <code>y</code> in <code>nums</code> such that <code>y % x</code> is not equal to <code>0</code>: The minimum achievable length in this case is <code>1</code> as well, because inserting <code>y % x</code> creates a new minimum, since <code>y % x < x</code>, returning to the first case.
If neither of the previous cases holds, and <code>x</code> occurs <code>cnt</code> times: The minimum length of <code>nums</code> achievable in this case is <code>ceil(cnt / 2)</code>.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Problems like this are common in technical interviews because they test mathematical insight, greedy reasoning, and pattern recognition. While the exact problem may vary, similar number-theory-based array reduction problems frequently appear in FAANG-style interviews.
The optimal approach uses a greedy observation based on the smallest element in the array. By checking divisibility relationships with the minimum value, we can determine whether the array can collapse to a single element or must retain multiple minimum elements. This avoids simulating operations directly and keeps the solution linear.
No complex data structures are required. A simple array traversal to track the minimum value and its frequency is enough. The rest of the logic relies on arithmetic checks such as divisibility.
The minimum element limits how much other numbers can be reduced during operations. If other numbers are not divisible by it, new smaller values can appear and eventually shrink the array significantly. If all numbers are multiples of it, reductions become restricted and the final size depends on how many minimum elements exist.