2344. Minimum Deletions to Make Array Divisible LeetCode Solution

In this guide, you will get 2344. Minimum Deletions to Make Array Divisible LeetCode Solution with the best time and space complexity. The solution to Minimum Deletions to Make Array Divisible problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Minimum Deletions to Make Array Divisible solution in C++
4. Minimum Deletions to Make Array Divisible solution in Java
5. Minimum Deletions to Make Array Divisible solution in Python
6. Additional Resources

Problem Statement of Minimum Deletions to Make Array Divisible

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 <= 105
1 <= nums[i], numsDivide[i] <= 109

Complexity Analysis

• Time Complexity: O(\texttt{sort})
• Space Complexity: O(\texttt{sort})

2344. Minimum Deletions to Make Array Divisible LeetCode Solution in C++

class Solution {
 public:
  int minOperations(vector<int>& nums, vector<int>& numsDivide) {
    const int gcd = getGCD(numsDivide);

    ranges::sort(nums);

    for (int i = 0; i < nums.size(); ++i)
      if (gcd % nums[i] == 0)
        return i;

    return -1;
  }

 private:
  int getGCD(const vector<int>& nums) {
    int gcd = nums[0];
    for (const int num : nums)
      gcd = __gcd(gcd, num);
    return gcd;
  }
};
/* code provided by PROGIEZ */

2344. Minimum Deletions to Make Array Divisible LeetCode Solution in Java

class Solution {
  public int minOperations(int[] nums, int[] numsDivide) {
    final int gcd = getGCD(numsDivide);

    Arrays.sort(nums);

    for (int i = 0; i < nums.length; ++i)
      if (gcd % nums[i] == 0)
        return i;

    return -1;
  }

  private int getGCD(int[] nums) {
    int g = nums[0];
    for (final int num : nums)
      g = gcd(g, num);
    return g;
  }

  private int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
  }
}
// code provided by PROGIEZ

2344. Minimum Deletions to Make Array Divisible LeetCode Solution in Python

class Solution:
  def minOperations(self, nums: list[int], numsDivide: list[int]) -> int:
    gcd = functools.reduce(math.gcd, numsDivide)

    for i, num in enumerate(sorted(nums)):
      if gcd % num == 0:
        return i

    return -1
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.