Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2344.html

2344. Minimum Deletions to Make Array Divisible

• Difficulty: Hard.
• Related Topics: Array, Math, Sorting, Heap (Priority Queue), Number Theory.
• Similar Questions: Check If Array Pairs Are Divisible by k.

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 <= 105

• 1 <= nums[i], numsDivide[i] <= 109

Solution

• Java
• Python
• C++
• Go

• class Solution {
      public int minOperations(int[] nums, int[] numsDivide) {
          int g = numsDivide[0];
          for (int i : numsDivide) {
              g = gcd(g, i);
          }
          int minOp = 0;
          int smallest = Integer.MAX_VALUE;
          for (int num : nums) {
              if (g % num == 0) {
                  smallest = Math.min(smallest, num);
              }
          }
          for (int num : nums) {
              if (num < smallest) {
                  ++minOp;
              }
          }
          return smallest == Integer.MAX_VALUE ? -1 : minOp;
      }
  
      private int gcd(int a, int b) {
          while (b > 0) {
              int tmp = a;
              a = b;
              b = tmp % b;
          }
          return a;
      }
  }
  
  ############
  
  class Solution {
      public int minOperations(int[] nums, int[] numsDivide) {
          int x = 0;
          for (int v : numsDivide) {
              x = gcd(x, v);
          }
          int y = 1 << 30;
          for (int v : nums) {
              if (x % v == 0) {
                  y = Math.min(y, v);
              }
          }
          if (y == 1 << 30) {
              return -1;
          }
          int ans = 0;
          for (int v : nums) {
              if (v < y) {
                  ++ans;
              }
          }
          return ans;
      }
  
      private int gcd(int a, int b) {
          return b == 0 ? a : gcd(b, a % b);
      }
  }
  

• class Solution:
      def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:
          x = gcd(*numsDivide)
          y = min((v for v in nums if x % v == 0), default=0)
          return sum(v < y for v in nums) if y else -1
  
  ############
  
  # 2344. Minimum Deletions to Make Array Divisible
  # https://leetcode.com/problems/minimum-deletions-to-make-array-divisible/
  
  class Solution:
      def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:
          nums.sort()
          
          d = numsDivide[0]
          
          for x in numsDivide:
              d = gcd(d, x)
              
          for i, x in enumerate(nums):
              if d % x == 0:
                  return i
          
          return -1
  
  

• class Solution {
  public:
      int minOperations(vector<int>& nums, vector<int>& numsDivide) {
          int x = 0;
          for (int& v : numsDivide) {
              x = gcd(x, v);
          }
          int y = 1 << 30;
          for (int& v : nums) {
              if (x % v == 0) {
                  y = min(y, v);
              }
          }
          if (y == 1 << 30) {
              return -1;
          }
          int ans = 0;
          for (int& v : nums) {
              ans += v < y;
          }
          return ans;
      }
  };
  

• func minOperations(nums []int, numsDivide []int) int {
  	x := 0
  	for _, v := range numsDivide {
  		x = gcd(x, v)
  	}
  	y := 1 << 30
  	for _, v := range nums {
  		if x%v == 0 {
  			y = min(y, v)
  		}
  	}
  	if y == 1<<30 {
  		return -1
  	}
  	ans := 0
  	for _, v := range nums {
  		if v < y {
  			ans++
  		}
  	}
  	return ans
  }
  
  func min(a, b int) int {
  	if a < b {
  		return a
  	}
  	return b
  }
  
  func gcd(a, b int) int {
  	if b == 0 {
  		return a
  	}
  	return gcd(b, a%b)
  }
  

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).

All Problems

All Solutions