Minimum deletions to make array divisible

Array Math Sorting Heap (Priority Queue) Number Theory

60.0% acceptance

Feb 25, 2026

586

131

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.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_operations(mut nums: Vec<i32>, nums_divide: Vec<i32>) -> i32 {
    let gcd = |mut a: i32, mut b: i32| -> i32 {
      while b != 0 { let t = b; b = a % b; a = t; }
      a
    };
    let g = nums_divide.iter().fold(nums_divide[0], |acc, &x| gcd(acc, x));
    nums.sort_unstable();
    for (i, &n) in nums.iter().enumerate() {
      if g % n == 0 { return i as i32; }
    }
    -1
  }
}