Minimum Deletions to Make Array Divisible

Hard

#2135Time: O(N * M + N log N), where `N` is the length of `nums` and `M` is the length of `numsDivide`. Sorting `nums` takes `O(N log N)`. The nested loops can run up to `N * M` times in the worst case (if all elements in `nums` are unique). This is likely to cause a 'Time Limit Exceeded' error for large inputs.Space: O(log N) or O(N), depending on the space used by the sorting algorithm. For an in-place sort like Heapsort it's O(1), for Quicksort it's O(log N) on average, and for Mergesort it's O(N).1 company

Patterns

Math Number Theory

Algorithms

Sorting

Data structures

Array Heap (Priority Queue)

Companies

Prompt

You are given two positive integer arrays nums and numsDivide. You can delete any number of elements from nums.

Return the minimum number of deletions such that the smallest element in nums divides all the elements of numsDivide. If this is not possible, return -1.

Note that an integer x divides y if y % x == 0.

Example 1:

Input: nums = [2,3,2,4,3], numsDivide = [9,6,9,3,15]
Output: 2
Explanation: 
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
Explanation: 
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 <= 10⁵
1 <= nums[i], numsDivide[i] <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through each unique candidate number from nums in ascending order. For each candidate, it checks if it divides every single element in numsDivide. The first candidate that satisfies this condition is the smallest possible one. The number of deletions would then be the count of elements in the original nums array that are smaller than this successful candidate.

Algorithm

Sort the nums array in non-decreasing order.
Iterate through the sorted nums array with index i from 0 to nums.length - 1.
To avoid re-checking for duplicate values, if i > 0 and nums[i] == nums[i-1], continue to the next iteration.
For the current element nums[i], check if it divides every element in numsDivide.
To do this, set a boolean flag isDivisor to true. Iterate through numsDivide. If d % nums[i] != 0 for any d in numsDivide, set isDivisor to false and break the inner loop.
If after checking all elements of numsDivide, isDivisor is still true, it means nums[i] is our target. Return the current index i.
If the outer loop completes without returning, it means no element in nums can divide all elements of numsDivide. Return -1.

Walkthrough

First, we sort the nums array to easily iterate through candidates in increasing order and to efficiently count deletions. We iterate through the sorted nums array. To avoid redundant checks for duplicate numbers, we skip a number if it's the same as the previous one. For each unique number num from nums, we assume it's our potential smallest element and check if it can divide all elements in numsDivide. We use a helper function or an inner loop for this check. If num divides all elements of numsDivide, we have found our target. Since we are iterating through the sorted nums array, this is the smallest such number. The number of deletions is its index i, which represents how many smaller elements came before it. We can return i. If we iterate through all of nums and no such number is found, it's impossible to satisfy the condition, so we return -1.

1import java.util.Arrays;2 3class Solution {4    public int minDeletions(int[] nums, int[] numsDivide) {5        Arrays.sort(nums);6        for (int i = 0; i < nums.length; i++) {7            // Skip duplicates to avoid redundant checks8            if (i > 0 && nums[i] == nums[i-1]) {9                continue;10            }11            12            int candidate = nums[i];13            boolean dividesAll = true;14            for (int div : numsDivide) {15                if (div % candidate != 0) {16                    dividesAll = false;17                    break;18                }19            }20            21            if (dividesAll) {22                return i;23            }24        }25        return -1;26    }27}

Complexity

Time

O(N * M + N log N), where `N` is the length of `nums` and `M` is the length of `numsDivide`. Sorting `nums` takes `O(N log N)`. The nested loops can run up to `N * M` times in the worst case (if all elements in `nums` are unique). This is likely to cause a 'Time Limit Exceeded' error for large inputs.

Space

O(log N) or O(N), depending on the space used by the sorting algorithm. For an in-place sort like Heapsort it's O(1), for Quicksort it's O(log N) on average, and for Mergesort it's O(N).

Trade-offs

Pros

Conceptually simple and easy to understand.
It correctly solves the problem for smaller inputs.

Cons

Inefficient due to the nested loop structure. For each unique element in nums, it iterates through the entire numsDivide array, which can be very slow if both arrays are large.

A more efficient approach leverages a mathematical property: if a number x divides all elements in a set, it must also divide their greatest common divisor (GCD). Instead of checking divisibility against every element in numsDivide, we can compute their GCD once and check potential candidates from nums against this single GCD value.

Algorithm

Define a helper function gcd(a, b) that computes the greatest common divisor of two numbers using the Euclidean algorithm.
Calculate the GCD of all elements in numsDivide. Initialize a variable g with numsDivide[0], then iterate through the rest of numsDivide, updating g = gcd(g, numsDivide[i]).
Sort the nums array in non-decreasing order.
Iterate through the sorted nums array with index i.
For each element nums[i], check if g % nums[i] == 0.
If the condition is met, nums[i] is the smallest number in nums that satisfies the property. The number of deletions is i. Return i.
If the loop finishes without finding such an element, return -1.

Walkthrough

The core idea is to find the smallest number in nums that divides the GCD of all elements in numsDivide. First, we calculate the GCD of all numbers in the numsDivide array. Let's call this g. The GCD can be computed iteratively: gcd(a, b, c) = gcd(gcd(a, b), c). If we find a number x in nums such that g % x == 0, then x is guaranteed to divide g. Since every number in numsDivide is a multiple of g, x will also divide every number in numsDivide. To find the minimum number of deletions, we need the smallest such x from nums. We sort the nums array in non-decreasing order. Then, we iterate through the sorted nums array. The first element nums[i] that divides g (i.e., g % nums[i] == 0) is our target. The number of deletions required to make nums[i] the smallest element is i, as all i elements before it are smaller and must be removed. If no element in nums divides g, it's impossible, so we return -1.

1import java.util.Arrays;2 3class Solution {4    private int gcd(int a, int b) {5        while (b != 0) {6            int temp = b;7            b = a % b;8            a = temp;9        }10        return a;11    }12 13    public int minDeletions(int[] nums, int[] numsDivide) {14        // 1. Find GCD of all elements in numsDivide15        int g = numsDivide[0];16        for (int i = 1; i < numsDivide.length; i++) {17            g = gcd(g, numsDivide[i]);18        }19        20        // 2. Sort nums to find the smallest valid number efficiently21        Arrays.sort(nums);22        23        // 3. Find the first number in sorted nums that divides the GCD24        for (int i = 0; i < nums.length; i++) {25            if (g % nums[i] == 0) {26                return i; // This is the number of deletions27            }28        }29        30        // 4. If no such number is found31        return -1;32    }33}

Complexity

Time

O(M * log(K) + N log N), where `N` is the length of `nums`, `M` is the length of `numsDivide`, and `K` is the maximum value in `numsDivide`. `O(M * log(K))` is for calculating the GCD of `numsDivide`. `O(N log N)` is for sorting `nums`. The final scan is `O(N)`. This is efficient enough to pass within the given constraints.

Space

O(log N) or O(N) for sorting, depending on the implementation. The GCD calculation is `O(1)` extra space.

Trade-offs

Pros

Highly efficient. The expensive check against all M elements of numsDivide is replaced by a single check against their GCD.
Reduces the time complexity significantly, making it feasible for large inputs.

Cons

Requires understanding the properties of the Greatest Common Divisor (GCD).

Solutions

Solution

1class Solution {2public3  int minOperations(int[] nums, int[] numsDivide) {4    int x = 0;5    for (int v : numsDivide) {6      x = gcd(x, v);7    }8    Arrays.sort(nums);9    for (int i = 0; i < nums.length; ++i) {10      if (x % nums[i] == 0) {11        return i;12      }13    }14    return -1;15  }16private17  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }18}

1class Solution:2    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

1class Solution {2public:3  int minOperations(vector<int> &nums, vector<int> &numsDivide) {4    int x = 0;5    for (int &v : numsDivide) {6      x = gcd(x, v);7    }8    sort(nums.begin(), nums.end());9    for (int i = 0; i < nums.size(); ++i) {10      if (x % nums[i] == 0) {11        return i;12      }13    }14    return -1;15  }16};

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem