Get this book -> Problems on Array: For Interviews and Competitive Programming

In this article, we will explore how we can get the minimum number of deletion of smallest element such that the smallest element in the first array divides all the elements in the second array. This will involve the concept of Min Heap and Hash Map.

Pre-requisites

- Basic maths
- Greatest Common Divisor (GCD)
- Min Heap
- Hash Map

### Problem statement

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.
```

### Observations

From the examples we can understand that the first array `nums`

is not sorted and it contains duplicates and we need the minimum number of deletions of minimum elements present in that array, hence it would be impossible to get the answer without some-sort of sorting.

The second observation is that we need a number which could divide all the elements in `numsDivide`

, a number and such a number is called the GCD of those numbers. GCD stands for Greatest Common Divisor.

We can use the inbuilt STL function `__gcd(a,b)`

to find the GCD of two numbers. Here `a`

and `b`

are the two numbers whose GCD has to be found.

### Approach - 1

This would be the most direct approach possible for this question.

**Intuitive Steps**

- First we will find the GCD of the
`numsDivide`

array. - Sort the given
`nums`

array. - Iterate through the array and check the condition
`gcd % nums[i] == 0`

, if yes return`i`

- Else return
`-1`

.

**Explained**

- We will to iterate over the
`numsDivide`

vector and find the GCD of all the numbers, we will use the in built function`__gcd()`

to compute the GCD of two numbers at an instance inside the`findGcd()`

. - The
`findGcd()`

accepts a vector and returns the GCD of all those numbers. To find it we will iterate over the array and pass in two values to the function, then in the second iteration we will pass the third value and the result of the first iteration into the function and so on. In the end we will return the GCD of the vector. - Now we will sort the
`nums`

vector and then we will iterate through the sorted`nums`

vector and check:- if
`gcd % nums[i] == 0`

, if it is the we will return`i`

. - else nothing gets returned then we will return
`-1`

after the`for`

loop.

- if

**Code:**

```
#include <bits/stdc++.h>
using namespace std;
int findGcd(vector<int>& v){
int a=v[0];
for(int i=1;i<v.size();i++){
int b=v[i];
a=__gcd(a,b);
}
return a;
}
int minOperations(vector<int>& nums, vector<int>& numsDivide) {
int gcd=findGcd(numsDivide);
sort(nums.begin(),nums.end());
for(int i=0;i<nums.size();i++){
if(gcd%nums[i]==0){
return i;
}
}
return -1;
}
int main() {
int n,m;
cout<<"Enter the nums vector: ";
cin>>n;
vector<int>nums;
cout<<"Enter "<<n<<" values: ";
while(n){
int temp;
n--;
cin>>temp;
nums.push_back(temp);
}
cout<<"Enter the numsDivide vector: ";
cin>>m;
vector<int>numsDivide;
cout<<"Enter "<<m<<" values";
while(m){
int temp;
m--;
cin>>temp;
numsDivide.push_back(temp);
}
cout<<minOperations(nums, numsDivide);
return 0;
}
```

The time complexity for the above code is `O(max(n,m)log n )`

, here `n`

is the size of `nums`

vector, and `m`

is the size of `numsDivide`

vector. The `log n`

in the time complexity occurs because of the sorting and it would be accompanied by the `max(n,m)`

, as we are iterating through both of them. So we can also say that real time complexity will be `O(n+m log n)`

. But both are literally the same. This program has `O(1)`

space complexity as it consumes no extra space.

### Approach - 2

Here also we will follow a similar approach.

**Intuitive Steps**

- Find the GCD of
`numsDivide`

vector. - Create a map.
- Enter all values in
`nums`

into the map. - Iterate through the map and check for the same condition.
- Keep a variable
`cnt`

and increment it by the key value of that element. - If condition satisfies return
`cnt`

. - Outside the loop return
`-1`

.

**Explained**

- First we will iterate through the
`numsDivide`

vector and find the GCD of all the elements in the array. - After getting GCD we will store the elements in
`nums`

, inside a`map`

where these element will be sorted and we will keep the count of each element next to it. - Now we will initialize a
`cnt`

variable to`0`

which will keep the track of, number of elements to delete. - Now we will iterate through the map and for each element we will check if
`gcd % element == 0`

:- If it is we will
`return`

the`cnt`

. - If its not we will add the count of that element to the
`cnt`

variable.

- If it is we will
- After the loop gets over then we will return
`-1`

as there will be no elements which would satisfy this condition.

**Code**

```
#include <bits/stdc++.h>
using namespace std;
int minOperations(vector<int>& nums, vector<int>& numsDivide) {
int gcd=numsDivide[0];
for(int i=1;i<numsDivide.size();i++){
gcd=__gcd(gcd,numsDivide[i]);
}
map<int,int>mp;
for(int i=0;i<nums.size();i++){
mp[nums[i]]++;
}
int cnt=0;
for(auto it:mp){
if(gcd%it.first==0){
return cnt;
}
cnt+=it.second;
}
return -1;
}
int main() {
int n,m;
cout<<"Enter the nums vector: ";
cin>>n;
vector<int>nums;
cout<<"Enter "<<n<<" values: ";
while(n){
int temp;
n--;
cin>>temp;
nums.push_back(temp);
}
cout<<"Enter the numsDivide vector: ";
cin>>m;
vector<int>numsDivide;
cout<<"Enter "<<m<<" values";
while(m){
int temp;
m--;
cin>>temp;
numsDivide.push_back(temp);
}
cout<<minOperations(nums, numsDivide);
return 0;
}
```

The time complexity to enter values into the map is `O(nlogn)`

and we are iterating over both the arrays, so we can say that the time complexity would be `O(max(n,m) * logn)`

where `n`

is the size of `numsDivide`

vector and m is the size of `nums`

vector. The space complexity of the solution is `O(n)`

which is size of the map.

### Approach - 3

In this approach we will use min-heap to obtain the answer.

**Intuitive Steps**

- Find the GCD of
`numsDivide`

array. - Create min-heap for the first array.
- Get and remove top elements from min heap till we get a number which divides the GCD.
- Track number of elements removed and return it.
- Return
`-1`

if we don't get a number which divides the GCD.

**Explained**

Here we will create a min-heap implemented using priority-queue. In a min-heap the minimum element will be at the top and largest element will be in the last position, so if we access the elements from the top to bottom we will get it in ascending order.

First we will find the GCD of the `numsDivide`

vector using the same method which we discussed in the previous approaches.

After that we will create a priority queue and, push all the elements in the `nums`

vector into it.

The next step is to initialize a `cnt`

variable to `0`

, which we will use to keep track of the number of elements removed.

Now till the priority-queue is not empty we will take the top element and check if `gcd % topElement == 0`

, if it is we will return `cnt`

.

Outside the loop we will return `-1`

, so that if the required element is not found then `-1`

would be returned.

**Code:**

```
#include <bits/stdc++.h>
using namespace std;
int minOperations(vector<int>& nums, vector<int>& numsDivide) {
int gcd=numsDivide[0];
for(int i=1;i<numsDivide.size();i++){
gcd=__gcd(gcd,numsDivide[i]);
}
priority_queue<int, vector<int>, greater<int>>mh;
for(int i:nums){
mh.push(i);
}
int cnt=0;
while(mh.size()>0){
if(gcd % mh.top() == 0)
return cnt;
++cnt;
mh.pop();
}
return -1;
}
int main() {
int n,m;
cout<<"Enter the nums vector: ";
cin>>n;
vector<int>nums;
cout<<"Enter "<<n<<" values: ";
while(n){
int temp;
n--;
cin>>temp;
nums.push_back(temp);
}
cout<<"Enter the numsDivide vector: ";
cin>>m;
vector<int>numsDivide;
cout<<"Enter "<<m<<" values";
while(m){
int temp;
m--;
cin>>temp;
numsDivide.push_back(temp);
}
cout<<minOperations(nums, numsDivide);
return 0;
}
```

The time complexity for the program is `O(n*logn)`

. This is because it takes `O(log n)`

time to inset an element into the priority queue, and it takes `O(n)`

time to traverse the array and also to loop through the priority queue. Since the calculation of GCD is also there, we can write the time complexity as `O(max(n,m) * logn)`

.

The space complexity of the program will be `O(n)`

where `n`

is the size of the `nums`

vector or the size of the priority queue.

### Output

```
Enter the nums vector: 5
Enter 5 values: 2 3 2 4 3
Enter the numsDivide vector: 5
Enter 5 values: 9 6 9 3 15
2
```

```
Enter the nums vector: 3
Enter 5 values: 4 3 6
Enter the numsDivide vector: 4
Enter 5 values: 8 2 6 10
-1
```

With this article at OpenGenus, you must have the complete idea of how to find minimum Deletions to Make Array Divisible.