# Minimum Deletions to Make Array Divisible
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-deletions-to-make-array-divisible)
Canonical: https://scaleengineer.com/dsa/problems/minimum-deletions-to-make-array-divisible
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [LinkedIn](https://scaleengineer.com/companies/linkedin)
---
## Problem
You are given two positive integer arrays `nums` and `numsDivide`. You can delete any number of elements from `nums`.

Return _the **minimum** number of deletions such that the **smallest** element in_ `nums` _**divides** all the elements of_ `numsDivide`. If this is not possible, return `-1`.

Note that an integer `x` divides `y` if `y % x == 0`.

**Example 1:**

**Input:** nums = [2,3,2,4,3], numsDivide = [9,6,9,3,15]
**Output:** 2
**Explanation:** 
The smallest element in [2,3,2,4,3] is 2, which does not divide all the elements of numsDivide.
We use 2 deletions to delete the elements in nums that are equal to 2 which makes nums = [3,4,3].
The smallest element in [3,4,3] is 3, which divides all the elements of numsDivide.
It can be shown that 2 is the minimum number of deletions needed.

**Example 2:**

**Input:** nums = [4,3,6], numsDivide = [8,2,6,10]
**Output:** -1
**Explanation:** 
We want the smallest element in nums to divide all the elements of numsDivide.
There is no way to delete elements from nums to allow this.

**Constraints:**

* `1 <= nums.length, numsDivide.length <= 105`
* `1 <= nums[i], numsDivide[i] <= 109`

# Approaches
## Brute Force by Checking Divisibility
This approach iterates through each unique candidate number from `nums` in ascending order. For each candidate, it checks if it divides every single element in `numsDivide`. The first candidate that satisfies this condition is the smallest possible one. The number of deletions would then be the count of elements in the original `nums` array that are smaller than this successful candidate.
**Time:** O(N * M + N log N), where `N` is the length of `nums` and `M` is the length of `numsDivide`. Sorting `nums` takes `O(N log N)`. The nested loops can run up to `N * M` times in the worst case (if all elements in `nums` are unique). This is likely to cause a 'Time Limit Exceeded' error for large inputs. · **Space:** O(log N) or O(N), depending on the space used by the sorting algorithm. For an in-place sort like Heapsort it's O(1), for Quicksort it's O(log N) on average, and for Mergesort it's O(N).
**Pros:** Conceptually simple and easy to understand.; It correctly solves the problem for smaller inputs.
**Cons:** Inefficient due to the nested loop structure. For each unique element in `nums`, it iterates through the entire `numsDivide` array, which can be very slow if both arrays are large.
### Explanation
First, we sort the `nums` array to easily iterate through candidates in increasing order and to efficiently count deletions. We iterate through the sorted `nums` array. To avoid redundant checks for duplicate numbers, we skip a number if it's the same as the previous one. For each unique number `num` from `nums`, we assume it's our potential smallest element and check if it can divide all elements in `numsDivide`. We use a helper function or an inner loop for this check. If `num` divides all elements of `numsDivide`, we have found our target. Since we are iterating through the sorted `nums` array, this is the smallest such number. The number of deletions is its index `i`, which represents how many smaller elements came before it. We can return `i`. If we iterate through all of `nums` and no such number is found, it's impossible to satisfy the condition, so we return -1.

```java
import java.util.Arrays;

class Solution {
    public int minDeletions(int[] nums, int[] numsDivide) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            // Skip duplicates to avoid redundant checks
            if (i > 0 && nums[i] == nums[i-1]) {
                continue;
            }
            
            int candidate = nums[i];
            boolean dividesAll = true;
            for (int div : numsDivide) {
                if (div % candidate != 0) {
                    dividesAll = false;
                    break;
                }
            }
            
            if (dividesAll) {
                return i;
            }
        }
        return -1;
    }
}
```
### Algorithm
- Sort the `nums` array in non-decreasing order.
- Iterate through the sorted `nums` array with index `i` from `0` to `nums.length - 1`.
- To avoid re-checking for duplicate values, if `i > 0` and `nums[i] == nums[i-1]`, continue to the next iteration.
- For the current element `nums[i]`, check if it divides every element in `numsDivide`.
- To do this, set a boolean flag `isDivisor` to `true`. Iterate through `numsDivide`. If `d % nums[i] != 0` for any `d` in `numsDivide`, set `isDivisor` to `false` and break the inner loop.
- If after checking all elements of `numsDivide`, `isDivisor` is still `true`, it means `nums[i]` is our target. Return the current index `i`.
- If the outer loop completes without returning, it means no element in `nums` can divide all elements of `numsDivide`. Return -1.

## Optimized Approach using Greatest Common Divisor (GCD)
A more efficient approach leverages a mathematical property: if a number `x` divides all elements in a set, it must also divide their greatest common divisor (GCD). Instead of checking divisibility against every element in `numsDivide`, we can compute their GCD once and check potential candidates from `nums` against this single GCD value.
**Time:** O(M * log(K) + N log N), where `N` is the length of `nums`, `M` is the length of `numsDivide`, and `K` is the maximum value in `numsDivide`. `O(M * log(K))` is for calculating the GCD of `numsDivide`. `O(N log N)` is for sorting `nums`. The final scan is `O(N)`. This is efficient enough to pass within the given constraints. · **Space:** O(log N) or O(N) for sorting, depending on the implementation. The GCD calculation is `O(1)` extra space.
**Pros:** Highly efficient. The expensive check against all `M` elements of `numsDivide` is replaced by a single check against their GCD.; Reduces the time complexity significantly, making it feasible for large inputs.
**Cons:** Requires understanding the properties of the Greatest Common Divisor (GCD).
### Explanation
The core idea is to find the smallest number in `nums` that divides the GCD of all elements in `numsDivide`. First, we calculate the GCD of all numbers in the `numsDivide` array. Let's call this `g`. The GCD can be computed iteratively: `gcd(a, b, c) = gcd(gcd(a, b), c)`. If we find a number `x` in `nums` such that `g % x == 0`, then `x` is guaranteed to divide `g`. Since every number in `numsDivide` is a multiple of `g`, `x` will also divide every number in `numsDivide`. To find the *minimum* number of deletions, we need the *smallest* such `x` from `nums`. We sort the `nums` array in non-decreasing order. Then, we iterate through the sorted `nums` array. The first element `nums[i]` that divides `g` (i.e., `g % nums[i] == 0`) is our target. The number of deletions required to make `nums[i]` the smallest element is `i`, as all `i` elements before it are smaller and must be removed. If no element in `nums` divides `g`, it's impossible, so we return -1.

```java
import java.util.Arrays;

class Solution {
    private int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public int minDeletions(int[] nums, int[] numsDivide) {
        // 1. Find GCD of all elements in numsDivide
        int g = numsDivide[0];
        for (int i = 1; i < numsDivide.length; i++) {
            g = gcd(g, numsDivide[i]);
        }
        
        // 2. Sort nums to find the smallest valid number efficiently
        Arrays.sort(nums);
        
        // 3. Find the first number in sorted nums that divides the GCD
        for (int i = 0; i < nums.length; i++) {
            if (g % nums[i] == 0) {
                return i; // This is the number of deletions
            }
        }
        
        // 4. If no such number is found
        return -1;
    }
}
```
### Algorithm
- Define a helper function `gcd(a, b)` that computes the greatest common divisor of two numbers using the Euclidean algorithm.
- Calculate the GCD of all elements in `numsDivide`. Initialize a variable `g` with `numsDivide[0]`, then iterate through the rest of `numsDivide`, updating `g = gcd(g, numsDivide[i])`.
- Sort the `nums` array in non-decreasing order.
- Iterate through the sorted `nums` array with index `i`.
- For each element `nums[i]`, check if `g % nums[i] == 0`.
- If the condition is met, `nums[i]` is the smallest number in `nums` that satisfies the property. The number of deletions is `i`. Return `i`.
- If the loop finishes without finding such an element, return -1.

# Solutions
### Java

```java
class Solution {
public
  int minOperations(int[] nums, int[] numsDivide) {
    int x = 0;
    for (int v : numsDivide) {
      x = gcd(x, v);
    }
    Arrays.sort(nums);
    for (int i = 0; i < nums.length; ++i) {
      if (x % nums[i] == 0) {
        return i;
      }
    }
    return -1;
  }
private
  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}

```

### Python

```python
class Solution:
    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int: x = numsDivide[0] for v in numsDivide[1:]: x = gcd(x, v) nums . sort() for i, v in enumerate(nums): if x % v == 0: return i return - 1

```

### CPP

```cpp
class Solution {
public:
  int minOperations(vector<int> &nums, vector<int> &numsDivide) {
    int x = 0;
    for (int &v : numsDivide) {
      x = gcd(x, v);
    }
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size(); ++i) {
      if (x % nums[i] == 0) {
        return i;
      }
    }
    return -1;
  }
};

```