Minimum Deletions to Make Array Divisible

Minimum Deletions to Make Array Divisible

1. What is this problem about?

The Minimum Deletions to Make Array Divisible problem involves two arrays: nums and numsDivide. The objective is to find the minimum number of elements to delete from nums such that the smallest remaining element in nums can divide every element in numsDivide. If no such element exists even after deleting elements, the answer is -1. This problem requires finding a common divisor for an entire set of numbers and then locating it (or a factor of it) in another set.

2. Why is this asked in interviews?

LinkedIn asks this "Hard" problem to test a candidate's proficiency in Number Theory and efficient array processing. The Minimum Deletions to Make Array Divisible interview question evaluates if you can identify that "dividing every element in a set" is equivalent to "dividing the Greatest Common Divisor (GCD) of that set." It also tests your ability to use sorting or heaps to find the smallest valid element with minimal deletions.

3. Algorithmic pattern used

The primary algorithmic pattern involves Math (GCD) and Sorting.

1. Calculate the GCD of all elements in numsDivide. Let this be $G$. Any number that divides all elements in numsDivide must also divide $G$.
2. Sort nums in ascending order.
3. Iterate through the sorted nums. The first element $x$ that satisfies $G \% x == 0$ is the smallest element we can keep.
4. The number of deletions is simply the count of elements in nums that are smaller than $x$. This "Array, Math, Number Theory, Sorting interview pattern" is efficient because the GCD calculation is $O(M \log(\max))$ and sorting is $O(N \log N)$.

4. Example explanation

nums = [4, 3, 2, 6], numsDivide = [8, 12, 16].

1. Calculate GCD of [8, 12, 16]: $GCD(8, 12) = 4$; $GCD(4, 16) = 4$. So $G = 4$.
2. Sort nums: [2, 3, 4, 6].
3. Check elements:
   • 2: $4 \% 2 == 0$. Valid!
   • Smallest valid element is 2.
4. Number of elements smaller than 2 in nums is 0. Deletions = 0. If nums was [3, 4, 6] and $G=4$:

• 3: $4 \% 3 \neq 0$.
• 4: $4 \% 4 == 0$. Valid!
• Deletions = 1 (the element 3).

5. Common mistakes candidates make

In the Minimum Deletions to Make Array Divisible coding problem, many candidates try to check every element in nums against every element in numsDivide, leading to an $O(N \times M)$ solution which is too slow. Another mistake is forgetting that the target must be the smallest element in the remaining nums. Some also struggle with calculating the GCD of more than two numbers or fail to handle the case where no element in nums divides $G$.

6. Interview preparation tip

Master the Euclidean algorithm for GCD and its property that $GCD(a, b, c) = GCD(a, GCD(b, c))$. This "Math-based interview pattern" is extremely useful for problems involving divisibility. Also, always consider sorting when you need to find the "first" or "smallest" element satisfying a condition in a pool of candidates.