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] <= 109To solve #2344 Minimum Deletions to Make Array Divisible, the key idea is to identify a value in nums that can divide every element in numsDivide. Instead of checking divisibility for each element separately, we can simplify the requirement by computing the greatest common divisor (GCD) of all elements in numsDivide. Any valid number from nums must divide this GCD.
After computing the GCD, sort nums and iterate from the smallest element. The first element that divides the computed GCD becomes the candidate that can divide all elements in numsDivide. The number of deletions equals the index of this element in the sorted array.
If no such element exists, the task is impossible and the answer is -1. Sorting ensures we minimize deletions, while the GCD step dramatically reduces repeated divisibility checks. A heap or priority queue can also be used to repeatedly access the smallest element, though sorting is typically simpler.
Time complexity mainly depends on computing the GCD and sorting the array, making the solution efficient even for large inputs.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| GCD + Sorting | O(n log n + m log V) | O(1) |
| GCD + Min Heap (Priority Queue) | O(n log n + m log V) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
How can we find an integer x that divides all the elements of numsDivide?
Will finding GCD (Greatest Common Divisor) help here?
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The optimal approach computes the GCD of all elements in numsDivide and then finds the smallest number in nums that divides this GCD. By sorting nums and scanning from the smallest value, we ensure the minimum number of deletions. If no number divides the GCD, the answer is -1.
Yes, this type of problem is common in technical interviews because it combines number theory with greedy thinking and array manipulation. Interviewers often use similar questions to test understanding of GCD, optimization strategies, and algorithmic efficiency.
Sorting the nums array is the most common approach because it allows us to check candidates in increasing order. Alternatively, a min heap or priority queue can be used to repeatedly extract the smallest element until a valid divisor is found.
If a number divides every element in numsDivide, it must also divide their greatest common divisor. Using the GCD reduces the problem to checking divisibility against a single number instead of the entire array, making the solution more efficient.