Problem

You are given two positive integer arrays nums and numsDivide. You can delete any number of elements from nums.

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

Examples

Example 1

1
2
3

Input: nums = [3,7,9], numsDivide = [3,9,6]
Output: 0
Explanation: 3 divides all elements in numsDivide. No deletions are needed.

Example 2

1
2
3

Input: nums = [4,3,6], numsDivide = [8,2,6,10]
Output: 2
Explanation: After deleting 4 and 6, nums = [3]. 3 does not divide 8, so return -1.

Example 3

1
2
3

Input: nums = [2,3,2,4,3], numsDivide = [9,6,9,3,15]
Output: 2
Explanation: After deleting two elements, nums = [3,3,3]. 3 divides all elements in numsDivide.

Constraints

  • 1 <= nums.length, numsDivide.length <= 10^5
  • 1 <= nums[i], numsDivide[i] <= 10^9

Solution

Method 1 – GCD and Sorting

Intuition

To make the smallest element in nums divide all elements in numsDivide, it must divide the GCD of numsDivide. We sort nums and try each element in increasing order, counting deletions until we find one that divides the GCD.

Approach

  1. Compute the GCD of all elements in numsDivide.
  2. Sort nums in ascending order.
  3. For each element in nums, if it divides the GCD, return the number of deletions so far.
  4. If no such element exists, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int minDeletions(vector<int>& nums, vector<int>& numsDivide) {
        int g = numsDivide[0];
        for (int x : numsDivide) g = gcd(g, x);
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); ++i) {
            if (g % nums[i] == 0) return i;
        }
        return -1;
    }
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}
func minDeletions(nums, numsDivide []int) int {
    g := numsDivide[0]
    for _, x := range numsDivide { g = gcd(g, x) }
    sort.Ints(nums)
    for i, x := range nums {
        if g%x == 0 { return i }
    }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int minDeletions(int[] nums, int[] numsDivide) {
        int g = numsDivide[0];
        for (int x : numsDivide) g = gcd(g, x);
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; ++i) {
            if (g % nums[i] == 0) return i;
        }
        return -1;
    }
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun minDeletions(nums: IntArray, numsDivide: IntArray): Int {
        fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
        var g = numsDivide[0]
        for (x in numsDivide) g = gcd(g, x)
        nums.sort()
        for ((i, x) in nums.withIndex()) {
            if (g % x == 0) return i
        }
        return -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def minDeletions(self, nums: list[int], numsDivide: list[int]) -> int:
        from math import gcd
        from functools import reduce
        g = reduce(gcd, numsDivide)
        nums.sort()
        for i, x in enumerate(nums):
            if g % x == 0:
                return i
        return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn min_deletions(nums: Vec<i32>, nums_divide: Vec<i32>) -> i32 {
        fn gcd(a: i32, b: i32) -> i32 {
            if b == 0 { a } else { gcd(b, a % b) }
        }
        let mut g = nums_divide[0];
        for &x in &nums_divide { g = gcd(g, x); }
        let mut nums = nums;
        nums.sort();
        for (i, &x) in nums.iter().enumerate() {
            if g % x == 0 { return i as i32; }
        }
        -1
    }
}
1
2
3
4

class Solution {
    minDeletions(nums: number[], numsDivide: number[]): number {
        function gcd(a: number, b: number): number {
            return b === 0 ? a : gcd(b, a % a