Minimize Length of Array Using Operations - Solution & Explanation
Problem Statement
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):
- Select two distinct indices
iandjfromnums, such thatnums[i] > 0andnums[j] > 0. - Insert the result of
nums[i] % nums[j]at the end ofnums. - Delete the elements at indices
iandjfromnums.
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] <= 109
Approach Overview
Problem Overview: You are given an array of positive integers. In one operation, you choose two elements and replace the larger one with the remainder of dividing it by the smaller value. The goal is to apply operations so that the final array length becomes as small as possible.
Approach 1: Use Hashing for Efficient Search (O(n) time, O(n) space)
The key observation comes from number theory. Let m be the minimum value in the array. Any operation involving m turns another number x into x % m. If there exists an element where x % m != 0, that remainder will be smaller than m, creating a new minimum and allowing further reductions until the array collapses to a single element. You scan the array once, track frequencies using a hash map, and check remainders against m. If every number is divisible by m, the only elements that remain relevant are those equal to m. The minimal length becomes ceil(count(m) / 2) because pairs of minimum values can eliminate each other through operations.
This approach relies on fast frequency lookup and a single pass through the array. It fits naturally with problems involving arrays and remainder properties.
Approach 2: Two Pointers Technique (O(n log n) time, O(1) extra space)
Another way to reason about the process is to sort the array and simulate reductions using a greedy strategy. After sorting, the smallest value sits at the beginning. Use two pointers to examine how the minimum interacts with the rest of the array. If a value produces a non-zero remainder with the minimum, that remainder becomes a new smallest value and the array can ultimately shrink to length 1. If all numbers are multiples of the minimum, only elements equal to the minimum matter for the final state. By grouping identical minimum values and pairing them greedily, you end up with ceil(count(m)/2) remaining elements.
This method emphasizes the greedy structure of the operations and is helpful if you prefer reasoning through sorted order and pointer movement. It also connects with common interview patterns using greedy algorithms.
Recommended for interviews: The hashing approach is typically the expected optimal solution because it derives the mathematical insight quickly and runs in O(n) time. Walking through the brute reasoning about modulo behavior demonstrates understanding, while identifying the minimum-element property and reducing the problem to counting shows strong algorithmic intuition.
Approach 1: Approach 1: Use Hashing for Efficient Search
This approach leverages a hash table (or dictionary) to efficiently keep track of elements. The main idea is to iterate through the list of numbers, check if the complement (based on the target value) exists in the hash table, and if not, add the current number to the hash table.
By using a hash table, we can achieve average O(1) time complexity for insertion and lookup operations.
This C solution implements a simple hash table using an array of linked lists to resolve hash collisions. The hash function computes the hash index using the remainder of the division of absolute values by a predefined size. On each iteration, we check if the complement is present in the hash table, and if not, we insert the current number with its index.
Complexity
Time Complexity: O(n) on average, where n is the number of elements since each insertion and lookup takes O(1) on average.
Space Complexity: O(n), due to the space required for the hash table to store elements.
Approach 2: Approach 2: Two Pointers Technique
This approach involves sorting the array and then using two pointers to efficiently find the two indices that sum up to the target. Begin by sorting the array; then initialize two pointers, one at the beginning ('left') and the other at the end ('right') of the sorted array. Adjust the pointers based on their sum until the target is found.
Note: This method entails returning indices of the values that sum up to the target rather than sorted positions.
This C program begins by copying the original array because sorting will rearrange its elements, damaging the index data. With the sorted array, adjust pointers until the desired sum is achieved. Afterward, iterate over the original array to find and return the original indices.
Complexity
Time Complexity: O(n log n), predominantly due to sorting, and O(n) for additional space needed to copy the array.
Approach 3: Case Discussion
Let's denote the smallest element in the array nums as mi.
If mi appears only once, we can perform operations with mi and the other elements in the array nums to eliminate all other elements, leaving only mi. The answer is 1.
If mi appears multiple times, we need to check whether all elements in the array nums are multiples of mi. If not, there exists at least one element x such that 0 < x bmod mi < mi. This means we can construct an element smaller than mi through operations. This smaller element can eliminate all other elements through operations, leaving only this smaller element. The answer is 1. If all elements are multiples of mi, we can first use mi to eliminate all elements larger than mi. The remaining elements are all mi, with a count of cnt. Pair them up, and perform an operation for each pair. Finally, there will be \lceil cnt / 2 \rceil elements left, so the answer is \lceil cnt / 2 \rceil.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Use Hashing for Efficient Search | Time Complexity: O(n) on average, where n is the number of elements since each insertion and lookup takes O(1) on average. |
| Approach 2: Two Pointers Technique | Time Complexity: O(n log n), predominantly due to sorting, and O(n) for additional space needed to copy the array. |
| Case Discussion | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hashing with Minimum Element Insight | O(n) | O(n) | General case; fastest solution when scanning array once and tracking frequencies |
| Two Pointers After Sorting | O(n log n) | O(1) | Useful when sorting is acceptable and you want to reason about reductions using ordered elements |
Video Solution
3012. Minimize Length of Array Using Operations | Cases Problem | Tricky • Aryan Mittal • 3,032 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimize Length of Array Using Operations easy or hard?
Minimize Length of Array Using Operations Python/Java solution
How to solve Minimize Length of Array Using Operations in O(n)?
What is the best approach for Minimize Length of Array Using Operations?
Is Minimize Length of Array Using Operations asked at Google/Amazon/Meta?
What data structure is used in Minimize Length of Array Using Operations?
What is the time complexity of Minimize Length of Array Using Operations?
Ready to solve this problem?
Practice Minimize Length of Array Using Operations with our built-in code editor and test cases.
Practice on FleetCode