LeetCode 2344 - Minimum Deletions to Make Array Divisible

LeetCode Problem 2344

Difficulty: 🔴 Hard
Topics: Array, Math, Sorting, Heap (Priority Queue), Number Theory

Solution

Problem Understanding

The problem gives us two arrays of positive integers, nums and numsDivide. We are allowed to delete any number of elements from nums, and our goal is to make the smallest remaining element in nums divide every number in numsDivide.

The key phrase here is smallest remaining element. After deletions, the minimum value left in nums becomes special, because that value must evenly divide every element in numsDivide.

In other words, suppose after deleting some values, the smallest number left in nums is x. Then for the solution to be valid:

numsDivide[i] % x == 0

for every element in numsDivide.

We want to minimize how many deletions are required to achieve this condition. If no element in nums can ever satisfy the divisibility requirement, then the answer is -1.

The input arrays can each contain up to 10^5 elements, and values can be as large as 10^9. These constraints immediately rule out expensive brute-force solutions. An algorithm with quadratic complexity such as O(n × m) where both arrays are large would be too slow.

An important observation is that the candidate smallest number must divide every element in numsDivide. That means it must divide their greatest common divisor (GCD). This mathematical property dramatically reduces the search space.

Several edge cases are important to think about upfront. If nums contains duplicates, deleting one occurrence may not be enough because the smallest remaining element matters. If no element in nums divides all elements in numsDivide, the answer must be -1. If the smallest element in sorted order already works, then no deletions are needed. Large values also mean we should avoid factorization or expensive divisibility checks across every possible candidate.

Approaches

Brute Force Approach

A straightforward approach is to try every possible candidate in nums as the smallest remaining element.

We could sort nums, then for each unique number x, check whether x divides every value in numsDivide. If it does, count how many smaller elements would need to be deleted so that x becomes the smallest remaining value.

This approach is correct because it explicitly checks every valid possibility. If a number can become the smallest valid divisor, we compute exactly how many deletions are needed and take the minimum.

However, the problem comes from efficiency. For each candidate in nums, we scan all of numsDivide.

If:

• n = len(nums)
• m = len(numsDivide)

then the time complexity becomes:

O(n × m)

With both arrays potentially reaching 10^5, this could require 10^10 operations in the worst case, which is far too slow.

Optimal Approach

The crucial mathematical insight is that a valid smallest element must divide every number in numsDivide.

Instead of checking divisibility against every element repeatedly, we can compute the GCD of all numbers in numsDivide.

Why does this help?

If a number x divides every element in numsDivide, then x must divide:

gcd(numsDivide)

Conversely, if x divides the GCD, then x automatically divides every number in numsDivide.

This transforms the problem into:

Find the smallest element in sorted nums that divides the GCD of numsDivide.

After sorting nums, we scan from smallest to largest. The first valid number we encounter is optimal because:

1. It minimizes deletions.
2. Any smaller numbers must be removed to make it the minimum.

If the valid number appears at index i in sorted order, then we must delete exactly i elements.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × m)	O(1)	Check every candidate against all elements in numsDivide
Optimal	O(m log V + n log n)	O(1) or O(log n)	Use GCD reduction and sorting

Here, V represents the maximum numeric value, because Euclid's GCD algorithm runs in logarithmic time.

Algorithm Walkthrough

Step 1: Compute the GCD of all elements in numsDivide

We first reduce numsDivide into a single number:

g = gcd(numsDivide[0], numsDivide[1], ..., numsDivide[n-1])

This works because any valid smallest element must divide all numbers, which means it must divide their GCD.

Step 2: Sort nums

We sort nums in ascending order.

The reason for sorting is that the problem depends on the smallest remaining element. By processing numbers from smallest to largest, the first valid candidate automatically produces the minimum number of deletions.

Step 3: Scan through sorted nums

For each number num in sorted order:

Check:

g % num == 0

If true, then num divides the GCD, which means it divides every element in numsDivide.

At that moment:

• Every earlier element is smaller than num
• Those smaller elements must be deleted
• Therefore, the index of num equals the number of deletions

Return that index immediately.

Step 4: Return -1 if no valid divisor exists

If we finish scanning nums without finding any valid divisor, then no sequence of deletions can satisfy the requirement.

Return:

-1

Why it works

The correctness comes from two properties.

First, a number divides all elements of numsDivide if and only if it divides their GCD. This means we only need one divisibility check per candidate.

Second, sorting guarantees optimality. Since we scan from smallest to largest, the first valid divisor minimizes deletions. Any later valid divisor would require deleting even more elements because all earlier values would still need removal.

Python Solution

from math import gcd
from typing import List

class Solution:
    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:
        # Compute GCD of numsDivide
        overall_gcd = numsDivide[0]

        for num in numsDivide[1:]:
            overall_gcd = gcd(overall_gcd, num)

        # Sort nums so we can find the first valid smallest element
        nums.sort()

        # Find first number that divides the GCD
        for index, num in enumerate(nums):
            if overall_gcd % num == 0:
                return index

        return -1

The implementation begins by computing the GCD of all elements in numsDivide. Instead of repeatedly checking divisibility against every number, we compress the divisibility condition into a single value called overall_gcd.

Next, we sort nums. Sorting is essential because the answer depends on which element becomes the smallest remaining number after deletions.

We then iterate through the sorted array. For each value, we test whether it divides the GCD. The first valid number immediately gives the answer because every smaller number must be removed.

If no valid divisor is found, the function returns -1.

Go Solution

package main

import "sort"

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func minOperations(nums []int, numsDivide []int) int {
	// Compute GCD of numsDivide
	overallGCD := numsDivide[0]

	for i := 1; i < len(numsDivide); i++ {
		overallGCD = gcd(overallGCD, numsDivide[i])
	}

	// Sort nums
	sort.Ints(nums)

	// Find first valid divisor
	for i, num := range nums {
		if overallGCD%num == 0 {
			return i
		}
	}

	return -1
}

The Go implementation follows the exact same logic as the Python version. Since Go does not include a built-in GCD function in the standard library for integers, we implement Euclid's algorithm manually.

Sorting is performed using sort.Ints(nums). Iteration through the sorted slice mirrors Python's enumerate.

Integer overflow is not a concern because all values remain within Go's integer limits for the given constraints, and the GCD operation only reduces numbers.

Worked Examples

Example 1

Input

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

Step 1: Compute GCD

Step	Current Number	Running GCD
Start	9	9
gcd(9, 6)	6	3
gcd(3, 9)	9	3
gcd(3, 3)	3	3
gcd(3, 15)	15	3

Final GCD:

g = 3

Step 2: Sort nums

[2,2,3,3,4]

Step 3: Scan for valid divisor

Index	Number	3 % Number	Valid?
0	2	1	No
1	2	1	No
2	3	0	Yes

We return:

2

This means deleting the two 2s.

Remaining array:

[3,3,4]

The smallest element is 3, and:

9 % 3 = 0
6 % 3 = 0
9 % 3 = 0
3 % 3 = 0
15 % 3 = 0

Answer:

2

Example 2

Input

nums = [4,3,6]
numsDivide = [8,2,6,10]

Step 1: Compute GCD

Step	Current Number	Running GCD
Start	8	8
gcd(8, 2)	2	2
gcd(2, 6)	6	2
gcd(2, 10)	10	2

Final GCD:

g = 2

Step 2: Sort nums

[3,4,6]

Step 3: Scan candidates

Index	Number	2 % Number	Valid?
0	3	2	No
1	4	2	No
2	6	2	No

No valid divisor exists.

Answer:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m log V + n log n)	Computing the GCD takes O(m log V), sorting nums takes O(n log n)
Space	O(1) or O(log n)	Only a few variables are used, sorting may require recursion stack space

The dominant cost comes from sorting nums. GCD computation is efficient because Euclid's algorithm runs in logarithmic time relative to the size of the numbers.

Since n can be 10^5, an O(n log n) approach is efficient enough for the problem constraints.

Test Cases

sol = Solution()

# Provided examples
assert sol.minOperations([2,3,2,4,3], [9,6,9,3,15]) == 2  # example 1
assert sol.minOperations([4,3,6], [8,2,6,10]) == -1  # example 2

# Already valid smallest element
assert sol.minOperations([2,4,6], [8,16,32]) == 0  # 2 already divides all

# Single element arrays
assert sol.minOperations([5], [10]) == 0  # single valid element
assert sol.minOperations([7], [10]) == -1  # single invalid element

# Duplicate values
assert sol.minOperations([2,2,2,3], [9,18,27]) == 3  # remove all 2s

# GCD equals one
assert sol.minOperations([2,3,5,7], [6,35]) == -1  # gcd is 1, no divisor exists
assert sol.minOperations([1,2,3], [6,10,15]) == 0  # 1 divides everything

# Large valid candidate
assert sol.minOperations([8,4,2], [16,32,64]) == 0  # smallest works

# Must skip several invalid candidates
assert sol.minOperations([10,15,20,25], [30,60,90]) == 1  # 15 works

# All elements invalid
assert sol.minOperations([7,11,13], [20,40,60]) == -1  # no divisor

# Multiple duplicates with first valid later
assert sol.minOperations([2,2,2,4,4,8], [8,16,32]) == 0  # 2 already works

Test Summary

Test	Why
Example 1	Validates standard successful case
Example 2	Validates impossible scenario
Smallest already valid	Ensures zero deletions work
Single element valid	Boundary condition
Single element invalid	Boundary failure case
Duplicate invalid values	Ensures repeated deletions counted correctly
GCD equals one	Tests hardest divisibility restriction
Value 1 exists	Confirms universal divisor behavior
Larger numbers	Verifies handling of bigger values
Delayed valid divisor	Ensures minimal deletion logic
No divisor exists	Confirms -1 behavior

Edge Cases

One important edge case occurs when the smallest element already satisfies the condition. For example:

nums = [2,4,6]
numsDivide = [8,16]

A buggy implementation might still perform deletions unnecessarily. Since 2 already divides every element, the correct answer is 0. Our implementation handles this because the sorted scan immediately succeeds at index 0.

Another tricky case is when duplicates appear before the valid divisor. Consider:

nums = [2,2,2,3]
numsDivide = [9,18]

The GCD is 9, and 2 does not divide 9. All three copies of 2 must be removed before 3 becomes the smallest element. Because we sort and return the first valid index, duplicates are automatically counted correctly.

A third edge case happens when no valid divisor exists. For example:

nums = [4,6,8]
numsDivide = [9,15]

The GCD is 3, and none of the values in nums divide 3. A naive implementation might accidentally return an incorrect deletion count or assume some subset works. Our algorithm safely scans every candidate and returns -1 when none divide the GCD.

Finally, the case where the GCD equals 1 deserves attention. Since only 1 divides 1, if nums does not contain 1, the answer must be -1. Our implementation naturally handles this because only 1 passes the divisibility check gcd_value % num == 0 when the GCD is 1.