{x}
blog image

Minimum Deletions to Make Array Divisible

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

Minimum Deletions to Make Array Divisible

This problem asks to find the minimum number of deletions needed from the nums array such that the smallest remaining element divides all elements in the numsDivide array. If it's impossible, return -1.

Approach

The core idea revolves around finding the greatest common divisor (GCD) of all elements in numsDivide. This GCD represents the smallest number that divides all elements in numsDivide. We then need to find the smallest element in nums that is a divisor of this GCD. The number of elements in nums smaller than this divisor will be the minimum deletions needed.

  1. Find GCD of numsDivide: Use the Euclidean algorithm to efficiently calculate the GCD of all numbers in numsDivide.

  2. Find the Smallest Divisor in nums: Iterate through the sorted nums array and find the first element that divides the GCD found in step 1.

  3. Count Deletions: Count the number of elements in nums that are smaller than the smallest divisor found in step 2. This count represents the minimum deletions required.

  4. Handle Impossible Cases: If no element in nums divides the GCD, it's impossible to satisfy the condition, so return -1.

Time Complexity Analysis

  • GCD Calculation: Calculating the GCD of n numbers takes O(n log M), where M is the maximum value in numsDivide. This is due to the logarithmic nature of the Euclidean algorithm.

  • Sorting: Sorting nums takes O(m log m), where m is the length of nums.

  • Iteration: Finding the smallest divisor and counting deletions takes O(m) time.

Therefore, the overall time complexity is O(n log M + m log m), where n is the length of numsDivide and m is the length of nums. The space complexity is dominated by sorting, resulting in O(log m) (for in-place sorting algorithms like merge sort or quicksort) or O(m) (for algorithms that require extra space like merge sort in some implementations).

Code Implementation (Python)

import math
 
def minOperations(nums, numsDivide):
    """
    Finds the minimum deletions to make the smallest element in nums divide all elements in numsDivide.
 
    Args:
        nums: A list of positive integers.
        numsDivide: A list of positive integers.
 
    Returns:
        The minimum number of deletions, or -1 if impossible.
    """
 
    # Find the GCD of numsDivide
    gcd_val = numsDivide[0]
    for i in range(1, len(numsDivide)):
        gcd_val = math.gcd(gcd_val, numsDivide[i])
 
    # Sort nums to efficiently find the smallest divisor
    nums.sort()
 
    # Find the smallest divisor in nums
    smallest_divisor = -1
    for num in nums:
        if gcd_val % num == 0:
            smallest_divisor = num
            break
 
    # If no divisor found, return -1
    if smallest_divisor == -1:
        return -1
 
    # Count deletions
    deletions = sum(1 for num in nums if num < smallest_divisor)
    return deletions

Other languages (Java, C++, Go) would follow a very similar structure, differing mainly in syntax and the specific implementation of the GCD function (some languages might have a built-in GCD function, others might require an explicit implementation of the Euclidean algorithm). The algorithmic approach remains consistent across all languages.