2344

2344. Minimum Deletions to Make Array Divisible (Hard)

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

Companies: LinkedIn

Related Topics:
Array, Math, Sorting, Heap (Priority Queue), Number Theory

Similar Questions:

• Check If Array Pairs Are Divisible by k (Medium)

Hints:

• How can we find an integer x that divides all the elements of numsDivide?
• Will finding GCD (Greatest Common Divisor) help here?

Solution 1.

• Get the GCD of all the numbers in B, say g
• Sort A
• Find the index of the first element that g % A[i] == 0
  • If found return i
  • Otherwise, return -1

// OJ: https://leetcode.com/problems/minimum-deletions-to-make-array-divisible
// Author: github.com/lzl124631x
// Time: O(B + AlogA)
// Space: O(1)
class Solution {
public:
    int minOperations(vector<int>& A, vector<int>& B) {
        int g = B[0], N = A.size();
        for (int n : B) g = gcd(n, g);
        sort(begin(A), end(A));
        for (int i = 0; i < N; ++i) {
            if (g % A[i] == 0) return i;
            while (i + 1 < N && A[i + 1] == A[i]) ++i;
        }
        return -1;
    }
};