Minimum Deletions to Make Array Divisible

Hard
1447.

Minimum Deletions to Make Array Divisible

Minimum Deletions to Make Array Divisible is a hard coding problem on arrays, math and sorting, asked in Amazon and Google interviews.

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^5
  • 1 <= nums[i], numsDivide[i] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number[]} numsDivide
 * @return {number}
 */
var minOperations = function(nums, numsDivide) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • 1 <= nums[i], numsDivide[i] <= 10^9

Hints for Minimum Deletions to Make Array Divisible

  1. Hint 1

    A number divides every element of numsDivide exactly when it divides their greatest common divisor.

  2. Hint 2

    Compute g = gcd(numsDivide) once.

  3. Hint 3

    Find the smallest x in nums with g % x == 0; the answer is how many elements of nums are smaller than x (they all have to go), or -1 if no such x.

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

  1. Compute g, the gcd of all of numsDivide, with Euclid's algorithm.
  2. Find the smallest value x in nums with g % x == 0. If none exists, return -1.
  3. Return the number of elements of nums strictly smaller than x.

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 of x itself stay.
  • Divisibility goes g % x == 0 — the element of nums is the divisor.
  • Sorting nums is not needed: one pass finds x, 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