Minimum Deletions to Make Array Divisible

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

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

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.

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

Minimum Deletions to Make Array Divisible [3 Solutions]

Algorithms heap hash map

Problem statement

Observations

Approach - 1

Approach - 2

Approach - 3

Output

CPU Core [Concept Explained]

Build torchvision from source