Watch 10 video solutions for Minimum Deletions to Make Array Divisible, a hard level problem involving Array, Math, Sorting. This walkthrough by Coding Decoded has 1,296 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1051 <= nums[i], numsDivide[i] <= 109Problem Overview: You are given two arrays: nums and numsDivide. Delete the minimum number of elements from nums so that the smallest remaining element divides every value in numsDivide. If no such element exists, return -1.
Approach 1: Sorting and GCD Check (O(n log n + m), Space: O(1))
The key observation: if a number divides every value in numsDivide, it must divide the GCD of the entire array. First compute g = gcd(numsDivide[0], numsDivide[1], ...). Then sort nums in ascending order. Iterate through the sorted array and find the first element x where g % x == 0. The index of that element equals the number of deletions required because all smaller elements must be removed. Sorting guarantees the smallest valid divisor is checked first. Time complexity is O(n log n + m), where n is the size of nums and m is the size of numsDivide. Space complexity stays O(1) if sorting is done in-place.
This approach combines concepts from sorting and math. The sorted order simplifies deletion counting because every element before the valid divisor must be removed.
Approach 2: GCD with Minimum Candidate Scan (O(n + m log V), Space: O(1))
Again compute the GCD of numsDivide, which takes O(m log V) where V is the maximum value. Instead of sorting, scan nums to identify elements that divide g. Track the smallest such candidate. If none exists, return -1. Once the smallest valid divisor x is known, make another pass through nums and count how many elements are smaller than x; those must be deleted. This avoids sorting and runs in O(n + m log V) time with constant extra space.
This method relies heavily on number theory insights. Any valid element must divide the global GCD, which drastically reduces the search space.
Recommended for interviews: The GCD-based reasoning is the core insight interviewers expect. Starting with the sorting approach shows solid problem decomposition and leads naturally to the optimal scan-based solution. Demonstrating that the divisor must divide the GCD of numsDivide proves strong understanding of number theory and typically leads to the most efficient implementation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and GCD Check | O(n log n + m) | O(1) | When sorting is acceptable and you want a simple implementation that directly counts deletions. |
| GCD with Minimum Candidate Scan | O(n + m log V) | O(1) | General case. Avoids sorting and gives the optimal linear scan once the GCD is known. |