Minimize Length of Array Using Operations

Med

#2680Time: O(N * log(K)) where N is the number of elements in `nums` and K is the maximum value in `nums`. The GCD calculation for the whole array dominates the complexity.Space: O(1) for an iterative GCD implementation.2 companies

Patterns

Math Greedy Number Theory

Data structures

Array

Companies

BNY Mellon HashedIn

Prompt

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 i and j from nums, such that nums[i] > 0 and nums[j] > 0.
Insert the result of nums[i] % nums[j] at the end of nums.
Delete the elements at indices 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 <= 10⁵
1 <= nums[i] <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This approach is based on the property that the smallest positive number that can be generated through the given operations is the greatest common divisor (GCD) of all numbers in the initial array. The final length of the array depends on whether this GCD is smaller than the initial minimum element.

Algorithm

Calculate g, the GCD of all elements in nums.
Find m, the minimum element in nums.
If g < m, return 1.
If g == m, count the occurrences of m in nums, let it be c.
Return (c + 1) / 2.

Walkthrough

The core idea is to analyze the set of numbers that can be generated. Any number created by the operation a % b is a linear combination of a and b. By extension, any number present in the array at any time is a linear combination of the initial numbers. The smallest positive integer that can be formed as a linear combination of a set of integers is their GCD.

Let g = gcd(nums[0], ..., nums[n-1]). We can always devise a sequence of operations to generate g and have it in our array. Once g is present, for any other number x in the array (which must be a multiple of g), we can perform the operation g % x. Since x >= g, g % x = g. This operation effectively replaces the pair (g, x) with a single g, reducing the array length by one. By repeating this, we can eliminate all other elements, leaving a single g. This leads to a final length of 1.

However, there's a special case. This reduction to length 1 is possible if we can generate a number smaller than any in the original array. This happens if g < min(nums). If g = min(nums), it means the minimum element m already divides all other numbers, and we cannot generate any positive number smaller than m. In this scenario, we can eliminate all numbers x > m by pairing them with m (using m % x = m), which leaves us with only copies of m. If we start with c copies of m, these can be paired up (m % m = 0) to reduce to a final set of ceil(c/2) elements.

Algorithm

Calculate g, the GCD of all elements in nums.
Find m, the minimum element in nums.
If g < m, it's possible to generate a number smaller than any initial element, which allows reducing the array to length 1. Return 1.
If g == m (note: g cannot be greater than m), count the occurrences of m in nums, let it be c.
The minimum length is ceil(c / 2), which can be calculated using integer arithmetic as (c + 1) / 2.

1class Solution {2    public int minimizeArrayLength(int[] nums) {3        int g = nums[0];4        for (int i = 1; i < nums.length; i++) {5            g = gcd(g, nums[i]);6        }7 8        int minVal = nums[0];9        for (int x : nums) {10            minVal = Math.min(minVal, x);11        }12 13        if (g < minVal) {14            return 1;15        } else { // g == minVal16            int countMin = 0;17            for (int x : nums) {18                if (x == minVal) {19                    countMin++;20                }21            }22            // This is equivalent to Math.ceil(countMin / 2.0)23            return (countMin + 1) / 2;24        }25    }26 27    private int gcd(int a, int b) {28        while (b != 0) {29            int temp = b;30            b = a % b;31            a = temp;32        }33        return a;34    }35}

Complexity

Time

O(N * log(K)) where N is the number of elements in `nums` and K is the maximum value in `nums`. The GCD calculation for the whole array dominates the complexity.

Space

O(1) for an iterative GCD implementation.

Trade-offs

Pros

Correctly solves the problem based on fundamental number theory properties.
Handles all cases logically.

Cons

Less efficient due to the computation of GCD for the entire array.
The log(max(nums)) factor in the time complexity can be slow if numbers are very large, although it's generally fast in practice.

This approach is an optimization of the GCD-based method. It avoids the explicit, and potentially costly, calculation of the GCD of the entire array by using a simple divisibility check against the minimum element.

Algorithm

Find the minimum element m in nums.
Iterate through nums. If any element x has x % m != 0, return 1.
If all elements are divisible by m, count the occurrences of m, let it be c.
Return (c + 1) / 2.

Walkthrough

The logic hinges on the same core principle: can we generate a positive number smaller than the initial minimum element? If yes, the answer is 1. If no, the answer depends on the count of the minimum element.

Instead of computing g = gcd(all nums) and comparing it with m = min(nums), we can achieve the same result more directly. We can generate a number smaller than m if and only if there is some element x in the array that is not divisible by m. If such an x exists, the operation x % m will produce a positive number smaller than m. This new smaller number can then be used to generate even smaller numbers, eventually leading to the generation of g = gcd(all nums). As established, once g is available, the array can be reduced to length 1.

If no such x exists, it means all elements in nums are divisible by m. This directly implies that m is the GCD of the array (m = g). In this case, as reasoned in the previous approach, we cannot generate a smaller positive number, and the minimum length is determined by the count of m.

Algorithm

Find the minimum element m in the array nums.
Iterate through nums and check if any element x is not divisible by m (i.e., x % m != 0).
If such an element is found, return 1.
If the loop completes without finding such an element, it means all elements are divisible by m. Count the number of times m appears in nums, let this be c.
Return ceil(c / 2), which is (c + 1) / 2 in integer arithmetic.

This method is more efficient as it replaces the O(N * log(K)) GCD calculation with simple O(N) scans.

1class Solution {2    public int minimizeArrayLength(int[] nums) {3        int minVal = Integer.MAX_VALUE;4        for (int x : nums) {5            minVal = Math.min(minVal, x);6        }7 8        // Check if we can generate a number smaller than minVal9        for (int x : nums) {10            if (x % minVal != 0) {11                // If x is not a multiple of minVal, then x % minVal is a new, smaller12                // positive number we can introduce. This eventually lets us generate the13                // GCD of the whole array, and reduce the array to size 1.14                return 1;15            }16        }17 18        // If we reach here, all numbers are divisible by minVal.19        // This means minVal is the GCD of the array. We cannot generate a smaller positive number.20        // The best we can do is reduce all elements > minVal, leaving only minVal's.21        // Then we reduce the minVal's by pairing them up.22        int countMin = 0;23        for (int x : nums) {24            if (x == minVal) {25                countMin++;26            }27        }28 29        // The number of elements after pairing up 'countMin' items is ceil(countMin / 2.0)30        return (countMin + 1) / 2;31    }32}

Complexity

Time

O(N), where N is the number of elements in `nums`. The algorithm involves a few linear scans of the array.

Space

O(1).

Trade-offs

Pros

Highly efficient with linear time complexity.
Simple to implement, avoiding complex GCD calculations.
Directly checks the condition for reducibility to 1.

Cons

The underlying logic relies on number theory insights that may not be immediately obvious.

Solutions

Solution

1class Solution { public int minimumArrayLength ( int [] nums ) { int mi = Arrays . stream ( nums ). min (). getAsInt (); int cnt = 0 ; for ( int x : nums ) { if ( x % mi != 0 ) { return 1 ; } if ( x == mi ) { ++ cnt ; } } return ( cnt + 1 ) / 2 ; } }

1class Solution { public: int minimumArrayLength ( vector < int >& nums ) { int mi = * min_element ( nums . begin (), nums . end ()); int cnt = 0 ; for ( int x : nums ) { if ( x % mi ) { return 1 ; } cnt += x == mi ; } return ( cnt + 1 ) / 2 ; } };

1class Solution : def minimumArrayLength ( self , nums : List [ int ]) -> int : mi = min ( nums ) if any ( x % mi for x in nums ): return 1 return ( nums . count ( mi ) + 1 ) // 2

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.

← Previous

Previous problem

Next problem

Solution

1class Solution { public int minimumArrayLength ( int [] nums ) { int mi = Arrays . stream ( nums ). min (). getAsInt (); int cnt = 0 ; for ( int x : nums ) { if ( x % mi != 0 ) { return 1 ; } if ( x == mi ) { ++ cnt ; } } return ( cnt + 1 ) / 2 ; } }

1class Solution { public: int minimumArrayLength ( vector < int >& nums ) { int mi = * min_element ( nums . begin (), nums . end ()); int cnt = 0 ; for ( int x : nums ) { if ( x % mi ) { return 1 ; } cnt += x == mi ; } return ( cnt + 1 ) / 2 ; } };

1class Solution : def minimumArrayLength ( self , nums : List [ int ]) -> int : mi = min ( nums ) if any ( x % mi for x in nums ): return 1 return ( nums . count ( mi ) + 1 ) // 2

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.