# 2344. Minimum Deletions to Make Array Divisible

## 题目

——“使数组可以被整除的最少删除次数”

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`

1.gcd如何求？可以自己实现辗转相除法，也可以使用系统版本。亲测效率差不多。

2.如何删除nums最小数字？可以使用堆排序（heapq），也可以排序。亲测直接排序要快上很多。

``````import fractions
class Solution(object):
def minOperations(self, nums, numsDivide):
"""
:type nums: List[int]
:type numsDivide: List[int]
:rtype: int
"""
nums.sort()
if nums[0] == 1:
return 0
g = numsDivide[0]
for n in numsDivide:
g = fractions.gcd(g, n)
if g == 1:
break

for i in range(len(nums)):
if g % nums[i] == 0:
return i
return -1``````

AC，收工。

——此处是内容的分割线——