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.

#2344

Hard

auto_awesome数组·数学

LeetCode 题解工作台

使数组可以被整除的最少删除次数

给你两个正整数数组 nums 和 numsDivide 。你可以从 nums 中删除任意数目的元素。请你返回使 nums 中最小元素可以整除 numsDivide 中所有元素的最少删除次数。如果无法得到这样的元素，返回 -1 。如果 y % x == 0 ，那么我们说整数 x 整除 y …

数组数学排序堆（优先队列）数论

题目描述

给你两个正整数数组 nums 和 numsDivide 。你可以从 nums 中删除任意数目的元素。

请你返回使 nums 中最小元素可以整除 numsDivide 中所有元素的最少删除次数。如果无法得到这样的元素，返回 -1 。

如果 y % x == 0 ，那么我们说整数 x 整除 y 。

示例 1：

输入：nums = [2,3,2,4,3], numsDivide = [9,6,9,3,15]
输出：2
解释：
[2,3,2,4,3] 中最小元素是 2 ，它无法整除 numsDivide 中所有元素。
我们从 nums 中删除 2 个大小为 2 的元素，得到 nums = [3,4,3] 。
[3,4,3] 中最小元素为 3 ，它可以整除 numsDivide 中所有元素。
可以证明 2 是最少删除次数。

示例 2：

输入：nums = [4,3,6], numsDivide = [8,2,6,10]
输出：-1
解释：
我们想 nums 中的最小元素可以整除 numsDivide 中的所有元素。
没有任何办法可以达到这一目的。

提示：

1 <= nums.length, numsDivide.length <= 10⁵
1 <= nums[i], numsDivide[i] <= 10⁹

lightbulb

解题思路

方法一：数学 + 排序

如果一个元素能整除数组 numsDivide 所有元素，那么这个元素是所有 $numsDivide[i]$ 的最大公约数 $x$ 的因子。因此，我们可以先求出 numsDivide 的最大公约数 $x$ 。

接下来，将数组 nums 排序，然后从头到尾遍历数组 nums，找到第一个是最大公约数 $x$ 的因子的元素，返回当前元素下标即可。

时间复杂度 $O(m + \log M + n \times \log n)$ ，其中 $n$ 和 $m$ 分别是数组 nums 和 numsDivide 的长度，而 $M$ 是数组 numsDivide 中的最大值。

实际上，我们也可以不用排序数组 nums，而是直接遍历数组 nums，找到最小的能整除 $x$ 的元素，然后我们再遍历一次数组 nums，统计小于等于这个元素的元素个数即可。

时间复杂度 $O(m + \log M + n)$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:
        x = numsDivide[0]
        for v in numsDivide[1:]:
            x = gcd(x, v)
        nums.sort()
        for i, v in enumerate(nums):
            if x % v == 0:
                return i
        return -1

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2280 表示一个折线图的最少线段数 #2607 使子数组元素和相等 #1998 数组的最大公因数排序