Skip to content

2344. Minimum Deletions to Make Array Divisible

Description

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

Solutions

Solution 1: Math + Sorting

Thinking

After deletions the remaining minimum must divide every entry of \(numsDivide\), hence it is a divisor of \(x=\gcd(numsDivide)\). \(n\) can be \(10^5\).

Compute \(x\), sort \(nums\), and return the index of the first divisor of \(x\). If none exists, the answer is \(-1\).

If an element can divide every value in numsDivide, it is a divisor of their GCD \(x\). Compute \(x\), sort nums, and return the index of the first divisor of \(x\).

The time complexity is \(O(m + \log M + n \times \log n)\), where \(n\) and \(m\) are the lengths of nums and numsDivide, and \(M\) is the maximum value in numsDivide.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:
        x = numsDivide[0]
        for v in numsDivide[1:]:
            x = gcd(x, v)
        nums.sort()
        for i, v in enumerate(nums):
            if x % v == 0:
                return i
        return -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minOperations(int[] nums, int[] numsDivide) {
        int x = 0;
        for (int v : numsDivide) {
            x = gcd(x, v);
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; ++i) {
            if (x % nums[i] == 0) {
                return i;
            }
        }
        return -1;
    }

    private 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
16
class Solution {
public:
    int minOperations(vector<int>& nums, vector<int>& numsDivide) {
        int x = 0;
        for (int& v : numsDivide) {
            x = gcd(x, v);
        }
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); ++i) {
            if (x % nums[i] == 0) {
                return i;
            }
        }
        return -1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func minOperations(nums []int, numsDivide []int) int {
    x := 0
    for _, v := range numsDivide {
        x = gcd(x, v)
    }
    sort.Ints(nums)
    for i, v := range nums {
        if x%v == 0 {
            return i
        }
    }
    return -1
}

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

Solution 2: Math + Enumeration (No Sorting)

Thinking

Method 1 sorts only to find the smallest valid divisor. A linear scan can take the minimum \(y\) that divides \(x\), then count values smaller than \(y\).

After computing the GCD \(x\) of numsDivide, scan nums for the smallest valid divisor \(y\), then count how many elements are smaller than \(y\). No sort is required.

The time complexity is \(O(m + \log M + n)\), and the space complexity is \(O(1)\).

1
2
3
4
5
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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 gcd(a, b int) int {
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}

Comments