##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2344.html

# 2344. Minimum Deletions to Make Array Divisible

• Difficulty: Hard.
• Related Topics: Array, Math, Sorting, Heap (Priority Queue), Number Theory.
• Similar Questions: Check If Array Pairs Are Divisible by k.

## 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

## Solution

• class Solution {
public int minOperations(int[] nums, int[] numsDivide) {
int g = numsDivide[0];
for (int i : numsDivide) {
g = gcd(g, i);
}
int minOp = 0;
int smallest = Integer.MAX_VALUE;
for (int num : nums) {
if (g % num == 0) {
smallest = Math.min(smallest, num);
}
}
for (int num : nums) {
if (num < smallest) {
++minOp;
}
}
return smallest == Integer.MAX_VALUE ? -1 : minOp;
}

private int gcd(int a, int b) {
while (b > 0) {
int tmp = a;
a = b;
b = tmp % b;
}
return a;
}
}

############

class Solution {
public int minOperations(int[] nums, int[] numsDivide) {
int x = 0;
for (int v : numsDivide) {
x = gcd(x, v);
}
int y = 1 << 30;
for (int v : nums) {
if (x % v == 0) {
y = Math.min(y, v);
}
}
if (y == 1 << 30) {
return -1;
}
int ans = 0;
for (int v : nums) {
if (v < y) {
++ans;
}
}
return ans;
}

private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}

• class Solution:
def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:
x = gcd(*numsDivide)
y = min((v for v in nums if x % v == 0), default=0)
return sum(v < y for v in nums) if y else -1

############

# 2344. Minimum Deletions to Make Array Divisible
# https://leetcode.com/problems/minimum-deletions-to-make-array-divisible/

class Solution:
def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:
nums.sort()

d = numsDivide[0]

for x in numsDivide:
d = gcd(d, x)

for i, x in enumerate(nums):
if d % x == 0:
return i

return -1


• class Solution {
public:
int minOperations(vector<int>& nums, vector<int>& numsDivide) {
int x = 0;
for (int& v : numsDivide) {
x = gcd(x, v);
}
int y = 1 << 30;
for (int& v : nums) {
if (x % v == 0) {
y = min(y, v);
}
}
if (y == 1 << 30) {
return -1;
}
int ans = 0;
for (int& v : nums) {
ans += v < y;
}
return ans;
}
};

• func minOperations(nums []int, numsDivide []int) int {
x := 0
for _, v := range numsDivide {
x = gcd(x, v)
}
y := 1 << 30
for _, v := range nums {
if x%v == 0 {
y = min(y, v)
}
}
if y == 1<<30 {
return -1
}
ans := 0
for _, v := range nums {
if v < y {
ans++
}
}
return ans
}

func min(a, b int) int {
if a < b {
return a
}
return b
}

func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}


Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).