We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Deletions to Make Array Divisible

Difficulty: Hard

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

Key Insights

  • We need to find the smallest element in nums after certain deletions.
  • The smallest element must divide all elements in numsDivide.
  • The problem can be approached by sorting nums and checking divisibility starting from the smallest element.
  • The number of deletions required is equal to the count of elements in nums that are less than the smallest element that divides all elements in numsDivide.

Space and Time Complexity

Time Complexity: O(n log n) for sorting the array, where n is the length of nums.
Space Complexity: O(1) if we sort in place, or O(n) for storing an additional array.

Solution

To solve the problem, we will:

  1. Calculate the GCD of all elements in numsDivide to find the maximum divisor that we need to check against.
  2. Sort the nums array.
  3. Iterate through the sorted nums to find the smallest element that divides the GCD of numsDivide.
  4. Count how many elements we need to delete to make this smallest element the minimum element in nums.

Code Solutions

from math import gcd
from functools import reduce

def min_deletions(nums, numsDivide):
    gcd_value = reduce(gcd, numsDivide)
    nums.sort()
    
    deletions = 0
    
    for num in nums:
        if gcd_value % num == 0:
            return deletions
        deletions += 1
    
    return -1
← Back to All Questions