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.
This approach involves sorting the nums array and then checking each element from the smallest to determine if it can divide all elements of numsDivide. Calculate the gcd of all elements in numsDivide, and then find the smallest element in nums that divides this gcd.
In this C solution, we first sort the nums array. Then, we calculate the GCD of numsDivide. We iterate through sorted nums, and for each element, we check if it divides the GCD. The first such element gives us the answer based on its index. If none exists, return -1.
Time Complexity: O(n log n + m), where n is the size of nums and m is the size of numsDivide. The sorting takes O(n log n), and the GCD computation takes O(m).
Space Complexity: O(1), no additional space is used except for variables.
In this approach, the aim is to compute the greatest common divisor (GCD) of the numsDivide array first and then identify the smallest number in nums that divides this GCD. This eliminates the need to sort nums, potentially improving efficiency in certain cases.
In this C solution, we first compute the GCD of the numsDivide array. Then, by iterating through nums, we look for the smallest element which divides the GCD. The result is the count of elements in nums less than this smallest element. If no such element is found, we return -1.
Time Complexity: O(m + n), where m is the size of numsDivide and n is the size of nums. GCD computation is O(m), and finding the minimal element fulfilling our requirements is O(n).
Space Complexity: O(1), since we use only a constant amount of additional space.
| Approach | Complexity |
|---|---|
| Sorting and GCD Check | Time Complexity: O(n log n + m), where n is the size of Space Complexity: O(1), no additional space is used except for variables. |
| Using GCD and Minimum Computation | Time Complexity: O(m + n), where m is the size of Space Complexity: O(1), since we use only a constant amount of additional space. |
| Default Approach | — |
| 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. |
Leetcode 2344 Minimum Deletions to Make Array Divisible | Maps • Coding Decoded • 1,296 views views
Watch 9 more video solutions →Practice Minimum Deletions to Make Array Divisible with our built-in code editor and test cases.
Practice on FleetCode