How to Solve Minimum Deletions to Make Array Divisible

The goal is to delete elements from nums so that the smallest remaining element divides all elements in numsDivide. If it's not possible, return -1. The problem focuses on mathematical divisibility combined with array manipulation.

Problem Statement

You are given two positive integer arrays nums and numsDivide. You can delete any number of elements from nums to make the smallest element in nums divide all elements in numsDivide.

Return the minimum number of deletions such that the smallest element in nums divides all the elements of numsDivide. If no solution exists, return -1. Note that an integer x divides y if y % x == 0.

Examples

Example 1

Input: nums = [2,3,2,4,3], numsDivide = [9,6,9,3,15]

Output: 2

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

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 <= 105
• 1 <= nums[i], numsDivide[i] <= 109

Solution Approach

Sorting and Divisibility Check

Sort the nums array. Start with the smallest element and check if it divides all elements of numsDivide. If it does, return the number of deletions required to remove elements smaller than this divisor. If no valid divisor is found, return -1.

GCD Optimization

Instead of checking each element individually, calculate the GCD (Greatest Common Divisor) of all elements in numsDivide. Check if any element in nums can divide this GCD, which is a more efficient approach than checking all combinations.

Greedy Deletion Strategy

Iterate through the sorted nums array, and for each element, check if it divides all elements in numsDivide. If it does, remove elements from nums that are smaller than this element. Track the number of deletions until a valid solution is found.

Complexity Analysis

The time complexity of the solution depends on sorting the nums array, which is O(n log n), where n is the length of nums. Checking divisibility or calculating GCDs is done in linear time O(m), where m is the length of numsDivide, resulting in an overall time complexity of O(n log n + m). The space complexity is O(n) due to the storage of the nums array and any temporary arrays or variables used in the approach.

What Interviewers Usually Probe

• Candidate understands how divisibility works and can relate array sorting to divisibility checks.
• Candidate efficiently handles large arrays and large numbers with mathematical optimization techniques.
• Candidate applies a strategic approach to array deletions and can justify the number of deletions required for valid solutions.

Common Pitfalls or Variants

Common pitfalls

• Failing to realize that sorting nums is essential for checking the smallest divisibility candidate first.
• Ignoring the potential to optimize by calculating the GCD of numsDivide before starting the divisibility checks.
• Overcomplicating the approach by trying unnecessary operations, such as brute force element deletion or not leveraging sorting.

Follow-up variants

• Instead of deleting elements to make the smallest divisor work, try solving the problem by keeping track of the largest divisor of numsDivide.
• Implement a dynamic programming approach where you progressively delete elements and check for divisibility at each step.
• Change the problem's condition by asking for the maximum number that divides all elements of numsDivide instead of the smallest.

How GhostInterview Helps

• GhostInterview provides tailored solutions to understand key problem patterns, such as array manipulation and number theory applications.
• It helps practice efficiently identifying the smallest divisor and implementing efficient algorithms for divisibility checks in array problems.
• GhostInterview supports solving optimization problems by recognizing when mathematical properties like GCD or sorting should be applied to reduce complexity.

Topic Pages

• Array
• Math
• Sorting
• Heap (Priority Queue)
• Number Theory

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the pattern behind the Minimum Deletions to Make Array Divisible problem?

The problem is a combination of array manipulation and number theory, focusing on divisibility. Sorting and GCD are key techniques to optimize the solution.

How can I optimize my solution for large arrays in this problem?

Sort the nums array and compute the GCD of numsDivide to reduce unnecessary checks, focusing on the most efficient divisibility conditions.

Is brute force an acceptable approach for solving this problem?

Brute force is not efficient due to the large possible input sizes. Optimizing with sorting, divisibility checks, and GCD is the best approach.

Can I use dynamic programming to solve Minimum Deletions to Make Array Divisible?

While dynamic programming could be applied to track deletions, sorting and GCD-based approaches are more efficient for this problem.

What is the time complexity of the best solution for this problem?

The optimal solution has a time complexity of O(n log n + m), where n is the length of nums and m is the length of numsDivide.