Minimum Deletions to Make Array Divisible — Solution
Minimum Deletions to Make Array Divisible solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Minimum Deletions to Make Array Divisible is a hard coding problem on arrays, math and sorting, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Math, Sorting, Number Theory
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given two arrays of positive integers, nums and numsDivide. You may delete any elements of nums.
Return the minimum number of deletions needed so that the smallest remaining element of nums divides every element of numsDivide. If that is impossible, return -1.
Example 1
Input: nums = [4,9,6,4,7], numsDivide = [12,18]
Output: 2
Explanation: Delete both 4s; the smallest remaining element, 6, divides 12 and 18.
Example 2
Input: nums = [2,3,2,4,3], numsDivide = [9,6,9,3,15]
Output: 2
Explanation: Delete both 2s; 3 divides every value.
Example 3
Input: nums = [4,3,6], numsDivide = [8,2,6,10]
Output: -1
Constraints
1 <= nums.length, numsDivide.length <= 10^51 <= nums[i], numsDivide[i] <= 10^9
Hints for Minimum Deletions to Make Array Divisible
Hint 1
A number divides every element of
numsDivideexactly when it divides their greatest common divisor.Hint 2
Compute
g = gcd(numsDivide)once.Hint 3
Find the smallest
xinnumswithg % x == 0; the answer is how many elements ofnumsare smaller thanx(they all have to go), or-1if no suchx.
How to solve Minimum Deletions to Make Array Divisible
Reduce numsDivide to its gcd g. The surviving minimum must divide g, and to delete as little as possible it should be the smallest element of nums that does — everything below it must be deleted, nothing else.
Approach
- Compute
g, the gcd of all ofnumsDivide, with Euclid's algorithm. - Find the smallest value
xinnumswithg % x == 0. If none exists, return-1. - Return the number of elements of
numsstrictly smaller thanx.
Why it works
x divides every element of numsDivide if and only if it divides their gcd. After deleting exactly the elements smaller than x, x is the minimum and works. Any valid outcome keeps some minimum y that divides g, and y >= x by the choice of x, so it deletes at least every element below x — no fewer deletions are possible.
Complexity
- Time —
O(n + m log V) - Space —
O(1)
Pitfalls
- Count deletions as elements strictly smaller than
x; copies ofxitself stay. - Divisibility goes
g % x == 0— the element ofnumsis the divisor. - Sorting
numsis not needed: one pass findsx, a second counts.
Reference solution
Python
from typing import List
from math import gcd
from functools import reduce
def minOperations(nums: List[int], numsDivide: List[int]) -> int:
g = reduce(gcd, numsDivide)
divisors = [x for x in nums if g % x == 0]
if not divisors:
return -1
smallest = min(divisors)
return sum(1 for x in nums if x < smallest)Java
public static int minOperations(int[] nums, int[] numsDivide) {
int g = 0;
for (int d : numsDivide) {
int a = g, b = d;
while (b != 0) {
int t = a % b;
a = b;
b = t;
}
g = a;
}
int smallest = -1;
for (int x : nums) if (g % x == 0 && (smallest < 0 || x < smallest)) smallest = x;
if (smallest < 0) return -1;
int deletions = 0;
for (int x : nums) if (x < smallest) deletions++;
return deletions;
}C++
static int mdGcd(int x, int y) { while (y) { int t = x % y; x = y; y = t; } return x; }
int minOperations(vector<int>& nums, vector<int>& numsDivide) {
int g = 0;
for (int d : numsDivide) g = mdGcd(g, d);
int smallest = -1;
for (int x : nums) if (g % x == 0 && (smallest < 0 || x < smallest)) smallest = x;
if (smallest < 0) return -1;
int deletions = 0;
for (int x : nums) if (x < smallest) deletions++;
return deletions;
}JavaScript
var minOperations = function(nums, numsDivide) {
var g = 0;
for (var i = 0; i < numsDivide.length; i++) {
var a = g, b = numsDivide[i];
while (b !== 0) {
var t = a % b;
a = b;
b = t;
}
g = a;
}
var smallest = -1;
for (var j = 0; j < nums.length; j++) {
if (g % nums[j] === 0 && (smallest < 0 || nums[j] < smallest)) smallest = nums[j];
}
if (smallest < 0) return -1;
var deletions = 0;
for (var k = 0; k < nums.length; k++) if (nums[k] < smallest) deletions++;
return deletions;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms