Minimize Length of Array Using Operations

Problem Description

You are given a 0-indexed array of positive integers. In each move you may pick two distinct indices i and j (with both numbers > 0), compute (nums[i] % nums[j]) and append the result to the array, then delete the two chosen numbers. Your goal is to perform any number of operations (possibly zero) so that the final array has minimum possible length. Return that minimum length.

Key Insights

• The operation is reminiscent of applying the Euclidean algorithm since taking a % b preserves the greatest common divisor (gcd). In all operations the gcd of the positive numbers is an invariant.
• Ultimately, any positive number that remains (if one is to “absorb” others) must be a multiple of the overall gcd; with careful use of the allowed ordering one can “convert” non‐gcd numbers into the gcd.
• If the array initially contains at least one element equal to the overall gcd then that number can serve as a “pivot” to convert any other positive number into the gcd without creating zeros.
• Once all positive numbers equal the gcd, pairing two of them (in any order) yields 0. However, 0 is “dead” (cannot be used in further operations). Thus there is a trade–off: while each valid operation reduces array length by one, using an operation on two gcd’s will eventually force the final array to consist of zeros (and possibly one leftover gcd) that can no longer be reduced.
• One can show that if we let c be the number of elements equal to the overall gcd (or, if none are initially equal to g, one extra operation guarantees a single copy of g) then the optimal strategy is to “convert” every non–g number into g and then pair copies of g. Pairing two g’s always yields 0 so that two copies are “compressed” into one element. Thus the optimal final length is given by: • If c > 0, the answer is (c/2) if c is even and ((c//2) + 1) if c is odd. • If no element is initially equal to g, we can generate one copy, so answer = 1.

Space and Time Complexity

Time Complexity: O(n · log(max(nums))) – to compute the gcd of n numbers. Space Complexity: O(1) – only a constant amount of extra space is used.

Solution

The first step is to compute the overall gcd, g, across the array because the gcd is invariant under the allowed operation. Next, count the number of elements in the array that are equal to g. If there is at least one occurrence the “pivot” exists and we can use it to convert all other numbers into g one by one without “wasting” any potential reduction (and without accidentally producing 0’s that might block further operations). (Note that if there is no element equal to g initially then one operation can produce a g – after that the answer will be computed as if there were exactly one g from the start.)

Once all positive numbers are g, the only available operation is pairing two copies of g. No matter which order is chosen, g % g is 0. Thus each such operation “removes” two copies of g and produces a 0. Since 0 is not eligible for further operations, these moves reduce the overall count by 1 each time. Pairing can be done as long as there are at least two positive elements. In the end the minimal final length is:   if c > 0 then final answer = floor(c/2) + (c mod 2)   if c = 0 then final answer = 1

This strategy leads to an optimal reduction in the array length.

Code Solutions

Below are sample implementations with line‐by–line comments.