How do you solve Minimum Deletions to Make Array Divisible on LeetCode?

Minimum Deletions to Make Array Divisible (LeetCode #2344) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(1) space complexity. Key insight: Finding the GCD of numsDivide helps in narrowing down the candidates for the smallest divisor.

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

The optimal solution for Minimum Deletions to Make Array Divisible runs in O(n log n) time and uses O(1) space. The sorting step dominates the complexity, while calculating the GCD is linear with respect to the size of numsDivide.

What is the brute force solution for Minimum Deletions to Make Array Divisible?

The brute force approach for Minimum Deletions to Make Array Divisible is Brute Force, with O(n²) time complexity and O(1) space complexity. We can try every possible combination of deletions from the nums array and check if the smallest remaining element divides all elements in numsDivide. This approach is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n log n).

What are the interview tips for Minimum Deletions to Make Array Divisible?

Always think about mathematical properties like GCD when dealing with divisibility problems. Optimize your solution by reducing the number of checks needed — sorting and using properties can help. Practice explaining your thought process clearly, as it shows your understanding of the problem.

What are common mistakes when solving Minimum Deletions to Make Array Divisible?

Not considering the GCD of numsDivide, leading to incorrect assumptions about divisibility. Failing to sort nums before searching for the smallest divisor.

#2344

Minimum Deletions to Make Array Divisible

Hard

ArrayMathSortingHeap (Priority Queue)Number TheoryMath (GCD, divisibility)Sorting

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(1)

💡

Intuition

Time O(n log n)Space O(1)

Instead of checking each element in nums, we can find the GCD of numsDivide. The smallest element in nums that divides this GCD will also divide all elements in numsDivide. This reduces our checks significantly.

⚙️

Algorithm

4 steps

1Step 1: Calculate the GCD of all elements in numsDivide.
2Step 2: Sort the nums array.
3Step 3: Find the smallest element in nums that divides the GCD.
4Step 4: Return the number of deletions needed to remove elements smaller than this smallest divisor.

solution.py14 lines

1# Full working Python code
2import math
3from functools import reduce
4
5def gcd(a, b):
6    return math.gcd(a, b)
7
8def min_deletions_optimal(nums, numsDivide):
9    gcd_value = reduce(gcd, numsDivide)
10    nums.sort()
11    for i in range(len(nums)):
12        if gcd_value % nums[i] == 0:
13            return i
14    return -1

ℹ

Complexity note: The sorting step dominates the complexity, while calculating the GCD is linear with respect to the size of numsDivide.

1Finding the GCD of numsDivide helps in narrowing down the candidates for the smallest divisor.
2Sorting nums allows us to efficiently find the smallest element that divides the GCD.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.