Is Minimum Deletions to Make Array Divisible easy or hard?

The problem is rated Hard on LeetCode mainly because the key insight is mathematical. Once you realize that any valid number must divide the GCD of numsDivide, the implementation becomes straightforward with sorting or a linear scan.

Minimum Deletions to Make Array Divisible Python/Java solution

In Python or Java, compute the GCD of numsDivide using iterative gcd calls. Then either sort nums and find the first value dividing the GCD or scan to find the smallest valid divisor and count elements smaller than it. Both implementations run efficiently within O(n log n + m) or better.

How to solve Minimum Deletions to Make Array Divisible in O(n)?

First compute the GCD of the numsDivide array. Then scan nums to find the smallest value that divides this GCD. After identifying that value, count how many elements in nums are smaller than it because those must be deleted. This approach runs in O(n + m log V) time and constant space.

What is the best approach for Minimum Deletions to Make Array Divisible?

The best approach computes the GCD of all elements in numsDivide and then finds the smallest element in nums that divides this GCD. If nums is sorted, the index of the first valid divisor gives the number of deletions. This approach runs in O(n log n + m) time or O(n + m log V) with a scan-based optimization.

Is Minimum Deletions to Make Array Divisible asked at Google/Amazon/Meta?

Problems involving GCD reasoning, divisibility, and array filtering frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test number theory insights and the ability to combine GCD computation with array processing.

What data structure is used in Minimum Deletions to Make Array Divisible?

The problem primarily uses arrays and mathematical operations. Sorting may be used to simplify deletion counting, while the core logic depends on GCD computation from number theory. No complex data structures beyond arrays are required.

What is the time complexity of Minimum Deletions to Make Array Divisible?

The common solution runs in O(n log n + m) time by sorting nums and computing the GCD of numsDivide. An optimized version avoids sorting and runs in O(n + m log V), where V is the maximum value used in the GCD computation. Space complexity is O(1).

Description Hints 2 Solution Video 6:07

2344. Minimum Deletions to Make Array Divisible

Hard61.8% acceptance3 companies

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 <= 10⁵
1 <= nums[i], numsDivide[i] <= 10⁹

Asked at 3 companies

Google Amazon

Topics

Hints open one at a time

Hint 1

How can we find an integer x that divides all the elements of numsDivide?

Hint 2

Will finding GCD (Greatest Common Divisor) help here?

6:07

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution