LeetCode Solutions Blog

Minimum Deletions to Make Array Divisible

Number: 2423

Difficulty: Hard

Paid? No

Companies: LinkedIn

Problem Description

Given two arrays, nums and numsDivide, we need to delete a minimum number of elements from nums such that the smallest remaining element divides all elements of numsDivide. If it’s impossible to achieve this, return -1.

Key Insights

The smallest element in nums must divide every element in numsDivide.
The greatest common divisor (GCD) of numsDivide is crucial because any candidate from nums must be a divisor of the GCD.
Compute the GCD of numsDivide; any valid candidate from nums must divide this GCD.
Sort nums in ascending order and iterate until finding the first element that divides the GCD.
The number of deletions corresponds to the index of that candidate in the sorted nums array.

Space and Time Complexity

Time Complexity: O(m + n log n)
Space Complexity: O(n)

Solution

Compute the GCD of all elements in numsDivide.
Sort the nums array.
Iterate over the sorted nums and count deletions until you find the first element (smallest candidate) that divides the GCD.
Return the count of deletions; if no candidate is found, return -1.

Code Solutions

# Import required modules for GCD and type hinting
import math
from typing import List

class Solution:
    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:
        # Compute the GCD of all numbers in numsDivide
        current_gcd = numsDivide[0]  # Initialize GCD with the first element
        for num in numsDivide[1:]:
            current_gcd = math.gcd(current_gcd, num)  # Update GCD
        
        # Sort nums to get the smallest candidate in order
        nums.sort()
        
        # Iterate through the sorted array while counting deletions
        deletion_count = 0
        for number in nums:
            # If a candidate divides the GCD, return the current count as answer
            if current_gcd % number == 0:
                return deletion_count
            deletion_count += 1
        
        # If no candidate divides the GCD, return -1
        return -1