Minimum Deletions to Make Array Divisible — LeetCode 2344 Python Solution

The problem

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

Example

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.

Python solution

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

Complexity

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2344. Minimum Deletions to Make Array Divisible is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Heap (Priority Queue).

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Related problems