Minimize the maximum of two arrays

Math Binary Search Number Theory

32.2% acceptance

Feb 25, 2026

523

101

We have two arrays arr1 and arr2 which are initially empty. You need to add positive integers to them such that they satisfy all the following conditions: arr1 contains uniqueCnt1 distinct positive integers, each of which is not divisible by divisor1. arr2 contains uniqueCnt2 distinct positive integers, each of which is not divisible by divisor2. No integer is present in both arr1 and arr2. Given divisor1, divisor2, uniqueCnt1, and uniqueCnt2, return the minimum possible maximum integer that can be present in either array.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

fn gcd(a: i64, b: i64) -> i64 {
  if b == 0 { a } else { gcd(b, a % b) }
}

fn lcm(a: i64, b: i64) -> i64 {
  a / gcd(a, b) * b
}

impl Solution {
  pub fn minimize_set(divisor1: i32, divisor2: i32, unique_cnt1: i32, unique_cnt2: i32) -> i32 {
    let d1 = divisor1 as i64;
    let d2 = divisor2 as i64;
    let c1 = unique_cnt1 as i64;
    let c2 = unique_cnt2 as i64;
    let lcm_val = lcm(d1, d2);

    let check = |m: i64| -> bool {
      (m - m / d1 >= c1) && (m - m / d2 >= c2) && (m - m / lcm_val >= c1 + c2)
    };

    let mut lo = 1i64;
    let mut hi = 2_000_000_000i64;
    while lo < hi {
      let mid = (lo + hi) / 2;
      if check(mid) {
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    lo as i32
  }
}