#2344

Hard

LeetCode Problem Workspace

Minimum Deletions to Make Array Divisible

Find the minimum number of deletions to make the smallest element in nums divide all elements of numsDivide.

array math sorting heap priority queue number theory

Problem Statement

You are given two positive integer arrays nums and numsDivide. You can delete any number of elements from nums to make the smallest element in nums divide all elements in numsDivide.

Return the minimum number of deletions such that the smallest element in nums divides all the elements of numsDivide. If no solution exists, return -1. Note that an integer x divides y if y % x == 0.

Examples

Example 1

Input: nums = [2,3,2,4,3], numsDivide = [9,6,9,3,15]

Output: 2

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

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

Solution Approach

Sorting and Divisibility Check

Sort the nums array. Start with the smallest element and check if it divides all elements of numsDivide. If it does, return the number of deletions required to remove elements smaller than this divisor. If no valid divisor is found, return -1.

GCD Optimization

Instead of checking each element individually, calculate the GCD (Greatest Common Divisor) of all elements in numsDivide. Check if any element in nums can divide this GCD, which is a more efficient approach than checking all combinations.

Greedy Deletion Strategy

Iterate through the sorted nums array, and for each element, check if it divides all elements in numsDivide. If it does, remove elements from nums that are smaller than this element. Track the number of deletions until a valid solution is found.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution depends on sorting the nums array, which is O(n log n), where n is the length of nums. Checking divisibility or calculating GCDs is done in linear time O(m), where m is the length of numsDivide, resulting in an overall time complexity of O(n log n + m). The space complexity is O(n) due to the storage of the nums array and any temporary arrays or variables used in the approach.

What Interviewers Usually Probe

Candidate understands how divisibility works and can relate array sorting to divisibility checks.
Candidate efficiently handles large arrays and large numbers with mathematical optimization techniques.
Candidate applies a strategic approach to array deletions and can justify the number of deletions required for valid solutions.

Common Pitfalls or Variants

Common pitfalls

Failing to realize that sorting nums is essential for checking the smallest divisibility candidate first.
Ignoring the potential to optimize by calculating the GCD of numsDivide before starting the divisibility checks.
Overcomplicating the approach by trying unnecessary operations, such as brute force element deletion or not leveraging sorting.

Follow-up variants

Instead of deleting elements to make the smallest divisor work, try solving the problem by keeping track of the largest divisor of numsDivide.
Implement a dynamic programming approach where you progressively delete elements and check for divisibility at each step.
Change the problem's condition by asking for the maximum number that divides all elements of numsDivide instead of the smallest.

FAQ

What is the pattern behind the Minimum Deletions to Make Array Divisible problem?

The problem is a combination of array manipulation and number theory, focusing on divisibility. Sorting and GCD are key techniques to optimize the solution.

How can I optimize my solution for large arrays in this problem?

Sort the nums array and compute the GCD of numsDivide to reduce unnecessary checks, focusing on the most efficient divisibility conditions.

Is brute force an acceptable approach for solving this problem?

Brute force is not efficient due to the large possible input sizes. Optimizing with sorting, divisibility checks, and GCD is the best approach.

Can I use dynamic programming to solve Minimum Deletions to Make Array Divisible?

While dynamic programming could be applied to track deletions, sorting and GCD-based approaches are more efficient for this problem.

What is the time complexity of the best solution for this problem?

The optimal solution has a time complexity of O(n log n + m), where n is the length of nums and m is the length of numsDivide.

terminal

Solution

Solution 1

#### Python3

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

Solution 2

#### Python3

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

Solution 3

#### Python3

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

Continue Practicing

#2280 minimum lines to represent a line chart #2607 make k subarray sums equal #1998 gcd sort of an array