Minimum Deletions to Make Array Divisible - Solution & Explanation

Q: Is Minimum Deletions to Make Array Divisible easy or hard?

The problem is rated Hard on LeetCode mainly because the key insight is mathematical. Once you realize that any valid number must divide the GCD of numsDivide, the implementation becomes straightforward with sorting or a linear scan.

Q: Minimum Deletions to Make Array Divisible Python/Java solution

In Python or Java, compute the GCD of numsDivide using iterative gcd calls. Then either sort nums and find the first value dividing the GCD or scan to find the smallest valid divisor and count elements smaller than it. Both implementations run efficiently within O(n log n + m) or better.

Q: How to solve Minimum Deletions to Make Array Divisible in O(n)?

First compute the GCD of the numsDivide array. Then scan nums to find the smallest value that divides this GCD. After identifying that value, count how many elements in nums are smaller than it because those must be deleted. This approach runs in O(n + m log V) time and constant space.

Q: What is the best approach for Minimum Deletions to Make Array Divisible?

The best approach computes the GCD of all elements in numsDivide and then finds the smallest element in nums that divides this GCD. If nums is sorted, the index of the first valid divisor gives the number of deletions. This approach runs in O(n log n + m) time or O(n + m log V) with a scan-based optimization.

Q: Is Minimum Deletions to Make Array Divisible asked at Google/Amazon/Meta?

Problems involving GCD reasoning, divisibility, and array filtering frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test number theory insights and the ability to combine GCD computation with array processing.

Q: What data structure is used in Minimum Deletions to Make Array Divisible?

The problem primarily uses arrays and mathematical operations. Sorting may be used to simplify deletion counting, while the core logic depends on GCD computation from number theory. No complex data structures beyond arrays are required.

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

The common solution runs in O(n log n + m) time by sorting nums and computing the GCD of numsDivide. An optimized version avoids sorting and runs in O(n + m log V), where V is the maximum value used in the GCD computation. Space complexity is O(1).

HardArray Math Sorting Heap (Priority Queue)15 min readAsked at: Amazon, Google, LinkedIn

Practice this problem

Problem Statement

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⁹

Approach Overview

Problem Overview: You are given two arrays: nums and numsDivide. Delete the minimum number of elements from nums so that the smallest remaining element divides every value in numsDivide. If no such element exists, return -1.

Approach 1: Sorting and GCD Check (O(n log n + m), Space: O(1))

The key observation: if a number divides every value in numsDivide, it must divide the GCD of the entire array. First compute g = gcd(numsDivide[0], numsDivide[1], ...). Then sort nums in ascending order. Iterate through the sorted array and find the first element x where g % x == 0. The index of that element equals the number of deletions required because all smaller elements must be removed. Sorting guarantees the smallest valid divisor is checked first. Time complexity is O(n log n + m), where n is the size of nums and m is the size of numsDivide. Space complexity stays O(1) if sorting is done in-place.

This approach combines concepts from sorting and math. The sorted order simplifies deletion counting because every element before the valid divisor must be removed.

Approach 2: GCD with Minimum Candidate Scan (O(n + m log V), Space: O(1))

Again compute the GCD of numsDivide, which takes O(m log V) where V is the maximum value. Instead of sorting, scan nums to identify elements that divide g. Track the smallest such candidate. If none exists, return -1. Once the smallest valid divisor x is known, make another pass through nums and count how many elements are smaller than x; those must be deleted. This avoids sorting and runs in O(n + m log V) time with constant extra space.

This method relies heavily on number theory insights. Any valid element must divide the global GCD, which drastically reduces the search space.

Recommended for interviews: The GCD-based reasoning is the core insight interviewers expect. Starting with the sorting approach shows solid problem decomposition and leads naturally to the optimal scan-based solution. Demonstrating that the divisor must divide the GCD of numsDivide proves strong understanding of number theory and typically leads to the most efficient implementation.

Approach 1: Sorting and GCD Check

This approach involves sorting the nums array and then checking each element from the smallest to determine if it can divide all elements of numsDivide. Calculate the gcd of all elements in numsDivide, and then find the smallest element in nums that divides this gcd.

In this C solution, we first sort the nums array. Then, we calculate the GCD of numsDivide. We iterate through sorted nums, and for each element, we check if it divides the GCD. The first such element gives us the answer based on its index. If none exists, return -1.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n log n + m), where n is the size of nums and m is the size of numsDivide. The sorting takes O(n log n), and the GCD computation takes O(m).

Space Complexity: O(1), no additional space is used except for variables.

Try this approach in the editor →

Approach 2: Using GCD and Minimum Computation

In this approach, the aim is to compute the greatest common divisor (GCD) of the numsDivide array first and then identify the smallest number in nums that divides this GCD. This eliminates the need to sort nums, potentially improving efficiency in certain cases.

In this C solution, we first compute the GCD of the numsDivide array. Then, by iterating through nums, we look for the smallest element which divides the GCD. The result is the count of elements in nums less than this smallest element. If no such element is found, we return -1.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(m + n), where m is the size of numsDivide and n is the size of nums. GCD computation is O(m), and finding the minimal element fulfilling our requirements is O(n).

Space Complexity: O(1), since we use only a constant amount of additional space.

Try this approach in the editor →

Approach 3: Default Approach

Code

Python Java C++Go

Python

Java

C++

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Sorting and GCD Check	Time Complexity: O(n log n + m), where n is the size of `nums` and m is the size of `numsDivide`. The sorting takes O(n log n), and the GCD computation takes O(m). Space Complexity: O(1), no additional space is used except for variables.
Using GCD and Minimum Computation	Time Complexity: O(m + n), where m is the size of `numsDivide` and n is the size of `nums`. GCD computation is O(m), and finding the minimal element fulfilling our requirements is O(n). Space Complexity: O(1), since we use only a constant amount of additional space.
Default Approach	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Sorting and GCD Check	O(n log n + m)	O(1)	When sorting is acceptable and you want a simple implementation that directly counts deletions.
GCD with Minimum Candidate Scan	O(n + m log V)	O(1)	General case. Avoids sorting and gives the optimal linear scan once the GCD is known.

Video Solution

Leetcode 2344 Minimum Deletions to Make Array Divisible | Maps • Coding Decoded • 1,337 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Deletions to Make Array Divisible easy or hard?

The problem is rated Hard on LeetCode mainly because the key insight is mathematical. Once you realize that any valid number must divide the GCD of numsDivide, the implementation becomes straightforward with sorting or a linear scan.

Minimum Deletions to Make Array Divisible Python/Java solution

In Python or Java, compute the GCD of numsDivide using iterative gcd calls. Then either sort nums and find the first value dividing the GCD or scan to find the smallest valid divisor and count elements smaller than it. Both implementations run efficiently within O(n log n + m) or better.

How to solve Minimum Deletions to Make Array Divisible in O(n)?

First compute the GCD of the numsDivide array. Then scan nums to find the smallest value that divides this GCD. After identifying that value, count how many elements in nums are smaller than it because those must be deleted. This approach runs in O(n + m log V) time and constant space.

What is the best approach for Minimum Deletions to Make Array Divisible?

The best approach computes the GCD of all elements in numsDivide and then finds the smallest element in nums that divides this GCD. If nums is sorted, the index of the first valid divisor gives the number of deletions. This approach runs in O(n log n + m) time or O(n + m log V) with a scan-based optimization.

Is Minimum Deletions to Make Array Divisible asked at Google/Amazon/Meta?

Problems involving GCD reasoning, divisibility, and array filtering frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test number theory insights and the ability to combine GCD computation with array processing.

What data structure is used in Minimum Deletions to Make Array Divisible?

The problem primarily uses arrays and mathematical operations. Sorting may be used to simplify deletion counting, while the core logic depends on GCD computation from number theory. No complex data structures beyond arrays are required.

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

The common solution runs in O(n log n + m) time by sorting nums and computing the GCD of numsDivide. An optimized version avoids sorting and runs in O(n + m log V), where V is the maximum value used in the GCD computation. Space complexity is O(1).

Ready to solve this problem?

Practice Minimum Deletions to Make Array Divisible with our built-in code editor and test cases.

Practice on FleetCode

Check If Array Pairs Are Divisible by k

Problem Info

DifficultyHard

Acceptance61.2%

Approaches3

Reading time15 min

Asked at

Amazon Google LinkedIn

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Sorting and GCD Check

Code

Complexity

Approach 2: Using GCD and Minimum Computation

Code

Complexity

Approach 3: Default Approach

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents