2344. Minimum Deletions to Make Array Divisible - Solution

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).

The problem

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.

Python

from math import gcd
from functools import reduce

def min_deletions(nums, numsDivide):
    nums.sort()
    gcd_val = reduce(gcd, numsDivide)
    for i, num in enumerate(nums):
        if gcd_val % num == 0:
            return i
    return -1

print(min_deletions([2, 3, 2, 4, 3], [9, 6, 9, 3, 15]))

Java

import java.util.*;

public class MinDeletions {
    public static int minDeletions(int[] nums, int[] numsDivide) {
        Arrays.sort(nums);
        int gcdVal = numsDivide[0];
        for (int num : numsDivide) {
            gcdVal = gcd(gcdVal, num);
        }
        for (int i = 0; i < nums.length; i++) {
            if (gcdVal % nums[i] == 0) {
                return i;
            }
        }
        return -1;
    }

    private static int gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 2, 4, 3};
        int[] numsDivide = {9, 6, 9, 3, 15};
        System.out.println(minDeletions(nums, numsDivide));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

int minDeletions(std::vector<int>& nums, std::vector<int>& numsDivide) {
    std::sort(nums.begin(), nums.end());
    int gcdValue = numsDivide[0];
    for (int i = 1; i < numsDivide.size(); ++i) {
        gcdValue = std::gcd(gcdValue, numsDivide[i]);
    }
    for (int i = 0; i < nums.size(); ++i) {
        if (gcdValue % nums[i] == 0) {
            return i;
        }
    }
    return -1;
}

int main() {
    std::vector<int> nums = {2, 3, 2, 4, 3};
    std::vector<int> numsDivide = {9, 6, 9, 3, 15};
    int result = minDeletions(nums, numsDivide);
    std::cout << result << std::endl;
    return 0;
}

JavaScript

function gcd(a, b) {
    while (b !== 0) {
        const t = b;
        b = a % b;
        a = t;
    }
    return a;
}

function minDeletions(nums, numsDivide) {
    nums.sort((a, b) => a - b);
    let gcdValue = numsDivide[0];
    for (let num of numsDivide) {
        gcdValue = gcd(gcdValue, num);
    }
    for (let i = 0; i < nums.length; i++) {
        if (gcdValue % nums[i] === 0) return i;
    }
    return -1;
}

console.log(minDeletions([2, 3, 2, 4, 3], [9, 6, 9, 3, 15]));

#include <stdio.h>
#include <stdlib.h>

int cmpfunc(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int gcd(int a, int b) {
    while (b != 0) {
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}

int gcdArray(int* array, int n) {
    int result = array[0];
    for (int i = 1; i < n; i++) {
        result = gcd(result, array[i]);
        if (result == 1) {
            return 1;
        }
    }
    return result;
}

int minDeletions(int* nums, int numsSize, int* numsDivide, int numsDivideSize) {
    qsort(nums, numsSize, sizeof(int), cmpfunc);
    int targetGCD = gcdArray(numsDivide, numsDivideSize);

    for (int i = 0; i < numsSize; i++) {
        if (nums[i] > targetGCD) continue;
        if (targetGCD % nums[i] == 0) {
            return i;
        }
    }
    return -1;
}

int main() {
    int nums[] = {2, 3, 2, 4, 3};
    int numsDivide[] = {9, 6, 9, 3, 15};
    int result = minDeletions(nums, 5, numsDivide, 5);
    printf("%d\n", result);
    return 0;
}

using System;
using System.Linq;

class Program {
    public static int MinDeletions(int[] nums, int[] numsDivide) {
        Array.Sort(nums);
        int gcdValue = numsDivide.Aggregate(GCD);
        for (int i = 0; i < nums.Length; i++) {
            if (gcdValue % nums[i] == 0) {
                return i;
            }
        }
        return -1;
    }

    private static int GCD(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    static void Main(string[] args) {
        int[] nums = {2, 3, 2, 4, 3};
        int[] numsDivide = {9, 6, 9, 3, 15};
        Console.WriteLine(MinDeletions(nums, numsDivide));
    }
}

This Python solution uses sorted() to sort nums and reduce() to obtain the gcd of numsDivide. It iterates over sorted nums to find the smallest element that divides the gcd and then returns its index, representing the minimum deletions. If none found, return -1.

Complexity

Time Complexity: O(n log n + m) where n is the size of nums and m is the size of numsDivide. Sorting takes O(n log n), and computing gcd of numsDivide takes O(m).

Space Complexity: O(1), with no additional space requirement beyond input arrays and simple 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.

Python

from math import gcd
from functools import reduce

def min_deletions(nums, numsDivide):
    gcd_val = reduce(gcd, numsDivide)
    min_val = float('inf')
    for num in nums:
        if gcd_val % num == 0:
            min_val = min(min_val, num)
    if min_val == float('inf'):
        return -1
    return sum(num < min_val for num in nums)

print(min_deletions([4, 3, 6], [8, 2, 6, 10]))

Java

import java.util.*;

public class MinDeletions {
    public static int minDeletions(int[] nums, int[] numsDivide) {
        int gcdValue = numsDivide[0];
        for (int num : numsDivide) {
            gcdValue = gcd(gcdValue, num);
        }
        int minVal = Integer.MAX_VALUE;
        for (int num : nums) {
            if (gcdValue % num == 0) {
                minVal = Math.min(minVal, num);
            }
        }
        if (minVal == Integer.MAX_VALUE) return -1;
        int deletions = 0;
        for (int num : nums) {
            if (num < minVal) deletions++;
        }
        return deletions;
    }

    private static int gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    public static void main(String[] args) {
        int[] nums = {4, 3, 6};
        int[] numsDivide = {8, 2, 6, 10};
        System.out.println(minDeletions(nums, numsDivide));
    }
}

C++

#include <iostream>
#include <vector>
#include <numeric>

int minDeletions(std::vector<int>& nums, std::vector<int>& numsDivide) {
    int gcdVal = numsDivide[0];
    for (int num : numsDivide) {
        gcdVal = std::gcd(gcdVal, num);
    }
    int minVal = INT_MAX;
    for (int num : nums) {
        if (gcdVal % num == 0) {
            minVal = std::min(minVal, num);
        }
    }
    if (minVal == INT_MAX) return -1;
    int deletions = 0;
    for (int num : nums) {
        if (num < minVal) ++deletions;
    }
    return deletions;
}

int main() {
    std::vector<int> nums = {4, 3, 6};
    std::vector<int> numsDivide = {8, 2, 6, 10};
    std::cout << minDeletions(nums, numsDivide) << std::endl;
    return 0;
}

JavaScript

function gcd(a, b) {
    while (b !== 0) {
        const t = b;
        b = a % b;
        a = t;
    }
    return a;
}

function minDeletions(nums, numsDivide) {
    let gcdValue = numsDivide.reduce((a, b) => gcd(a, b));
    let minValue = Infinity;
    for (let num of nums) {
        if (gcdValue % num === 0) {
            minValue = Math.min(minValue, num);
        }
    }
    if (minValue === Infinity) return -1;
    return nums.filter(num => num < minValue).length;
}

console.log(minDeletions([4, 3, 6], [8, 2, 6, 10]));

#include <stdio.h>

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int gcdArray(int* arr, int n) {
    int ret = arr[0];
    for (int i = 1; i < n; ++i) {
        ret = gcd(ret, arr[i]);
    }
    return ret;
}

int minDeletions(int* nums, int numsSize, int* numsDivide, int numsDivideSize) {
    int gcdVal = gcdArray(numsDivide, numsDivideSize);
    int minVal = 1000000001; // Given constraints 1 <= nums[i] <= 10^9
    for (int i = 0; i < numsSize; ++i) {
        if (gcdVal % nums[i] == 0 && nums[i] < minVal) {
            minVal = nums[i];
        }
    }
    if (minVal == 1000000001) return -1;
    int deletions = 0;
    for (int i = 0; i < numsSize; ++i) {
        if (nums[i] < minVal) ++deletions;
    }
    return deletions;
}

int main() {
    int nums[] = {4, 3, 6};
    int numsDivide[] = {8, 2, 6, 10};
    int result = minDeletions(nums, 3, numsDivide, 4);
    printf("%d\n", result);
    return 0;
}

using System;
using System.Linq;

public class Solution {
    public int MinDeletions(int[] nums, int[] numsDivide) {
        int gcdValue = numsDivide.Aggregate(GCD);
        int minValue = int.MaxValue;
        foreach (var num in nums) {
            if (gcdValue % num == 0) {
                minValue = Math.Min(minValue, num);
            }
        }
        if (minValue == int.MaxValue) return -1;
        return nums.Count(num => num < minValue);
    }

    private int GCD(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    public static void Main() {
        int[] nums = {4, 3, 6};
        int[] numsDivide = {8, 2, 6, 10};
        Solution sol = new Solution();
        Console.WriteLine(sol.MinDeletions(nums, numsDivide));
    }
}

The Python solution calculates the GCD of numsDivide and evaluates nums to discover the smallest number dividing this GCD. It counts elements lesser than this to assess deletion requirements. If no such number is found in nums, it returns -1.

Complexity

Time Complexity: O(m + n), where m derives from GCD calculation and n from evaluating nums.

Space Complexity: O(1), reflecting stable space usage beyond core arrays and variables.

Try this approach in the editor

Approach 3: Default Approach

func minOperations(nums []int, numsDivide []int) int {
	x := 0
	for _, v := range numsDivide {
		x = gcd(x, v)
	}
	sort.Ints(nums)
	for i, v := range nums {
		if x%v == 0 {
			return i
		}
	}
	return -1
}

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

Try this approach in the editor

Complexity comparison

Approach Complexity

Sorting and GCD Check

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`. Sorting takes O(n log n), and computing gcd of `numsDivide` takes O(m). Space Complexity: O(1), with no additional space requirement beyond input arrays and simple variables.
Using GCD and Minimum Computation	Time Complexity: O(m + n), where m derives from GCD calculation and n from evaluating `nums`. Space Complexity: O(1), reflecting stable space usage beyond core arrays and variables.
Default Approach	–

Time Complexity: O(n log n + m) where n is the size of nums and m is the size of numsDivide. Sorting takes O(n log n), and computing gcd of numsDivide takes O(m).

Space Complexity: O(1), with no additional space requirement beyond input arrays and simple variables.

Using GCD and Minimum Computation

Time Complexity: O(m + n), where m derives from GCD calculation and n from evaluating nums.

Space Complexity: O(1), reflecting stable space usage beyond core arrays and variables.

Default Approach –

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.

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).

Minimum Deletions to Make Array Divisible solution and explanation

The problem

Approach overview

Approach 1: Sorting and GCD Check

Approach 2: Using GCD and Minimum Computation

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Minimum Deletions to Make Array Divisible solution and explanation

The problem

Approach overview

Approach 1: Sorting and GCD Check

Approach 2: Using GCD and Minimum Computation

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems