# Minimize Length of Array Using Operations
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimize-length-of-array-using-operations)
Canonical: https://scaleengineer.com/dsa/problems/minimize-length-of-array-using-operations
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Data structures:** Array
**Companies:** [BNY Mellon](https://scaleengineer.com/companies/bny-mellon), [HashedIn](https://scaleengineer.com/companies/hashedin)
---
## Problem
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 <= 105`
* `1 <= nums[i] <= 109`

# Approaches
## GCD Calculation Approach
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.
**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.
**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.
### Explanation
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
1.  Calculate `g`, the GCD of all elements in `nums`.
2.  Find `m`, the minimum element in `nums`.
3.  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.
4.  If `g == m` (note: `g` cannot be greater than `m`), count the occurrences of `m` in `nums`, let it be `c`.
5.  The minimum length is `ceil(c / 2)`, which can be calculated using integer arithmetic as `(c + 1) / 2`.

```java
class Solution {
    public int minimizeArrayLength(int[] nums) {
        int g = nums[0];
        for (int i = 1; i < nums.length; i++) {
            g = gcd(g, nums[i]);
        }

        int minVal = nums[0];
        for (int x : nums) {
            minVal = Math.min(minVal, x);
        }

        if (g < minVal) {
            return 1;
        } else { // g == minVal
            int countMin = 0;
            for (int x : nums) {
                if (x == minVal) {
                    countMin++;
                }
            }
            // This is equivalent to Math.ceil(countMin / 2.0)
            return (countMin + 1) / 2;
        }
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}
```
### 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`.

## Minimum Element Divisibility Check
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.
**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).
**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.
### Explanation
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
1.  Find the minimum element `m` in the array `nums`.
2.  Iterate through `nums` and check if any element `x` is not divisible by `m` (i.e., `x % m != 0`).
3.  If such an element is found, return 1.
4.  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`.
5.  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.

```java
class Solution {
    public int minimizeArrayLength(int[] nums) {
        int minVal = Integer.MAX_VALUE;
        for (int x : nums) {
            minVal = Math.min(minVal, x);
        }

        // Check if we can generate a number smaller than minVal
        for (int x : nums) {
            if (x % minVal != 0) {
                // If x is not a multiple of minVal, then x % minVal is a new, smaller
                // positive number we can introduce. This eventually lets us generate the
                // GCD of the whole array, and reduce the array to size 1.
                return 1;
            }
        }

        // If we reach here, all numbers are divisible by minVal.
        // This means minVal is the GCD of the array. We cannot generate a smaller positive number.
        // The best we can do is reduce all elements > minVal, leaving only minVal's.
        // Then we reduce the minVal's by pairing them up.
        int countMin = 0;
        for (int x : nums) {
            if (x == minVal) {
                countMin++;
            }
        }

        // The number of elements after pairing up 'countMin' items is ceil(countMin / 2.0)
        return (countMin + 1) / 2;
    }
}
```
### 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`.

# Solutions
### Java

```java
class 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 ; } }
```

### CPP

```cpp
class 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 ; } };
```

### Python

```python
class 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
```