2513. Minimize the Maximum of Two Arrays LeetCode Solution

In this guide, you will get 2513. Minimize the Maximum of Two Arrays LeetCode Solution with the best time and space complexity. The solution to Minimize the Maximum of Two Arrays 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.

Problem Statement
Complexity Analysis
Minimize the Maximum of Two Arrays solution in C++
Minimize the Maximum of Two Arrays solution in Java
Minimize the Maximum of Two Arrays solution in Python
Additional Resources

2513. Minimize the Maximum of Two Arrays LeetCode Solution image

Problem Statement of Minimize the Maximum of Two Arrays

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.

Example 1:

Input: divisor1 = 2, divisor2 = 7, uniqueCnt1 = 1, uniqueCnt2 = 3
Output: 4
Explanation:
We can distribute the first 4 natural numbers into arr1 and arr2.
arr1 = [1] and arr2 = [2,3,4].
We can see that both arrays satisfy all the conditions.
Since the maximum value is 4, we return it.

Example 2:

Input: divisor1 = 3, divisor2 = 5, uniqueCnt1 = 2, uniqueCnt2 = 1
Output: 3
Explanation:
Here arr1 = [1,2], and arr2 = [3] satisfy all conditions.
Since the maximum value is 3, we return it.
Example 3:

Input: divisor1 = 2, divisor2 = 4, uniqueCnt1 = 8, uniqueCnt2 = 2
Output: 15
Explanation:
Here, the final possible arrays can be arr1 = [1,3,5,7,9,11,13,15], and arr2 = [2,6].
It can be shown that it is not possible to obtain a lower maximum satisfying all conditions.

Constraints:

2 <= divisor1, divisor2 <= 105
1 <= uniqueCnt1, uniqueCnt2 < 109
2 <= uniqueCnt1 + uniqueCnt2 <= 109

Complexity Analysis

Time Complexity: O(\log 2^{31})
Space Complexity: O(1)

2513. Minimize the Maximum of Two Arrays LeetCode Solution in C++

class Solution {
 public:
  int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
    const long divisorLcm = std::lcm(static_cast<long>(divisor1), divisor2);
    long l = 0;
    long r = INT_MAX;

    while (l < r) {
      const long m = (l + r) / 2;
      if (isPossible(m, divisorLcm, divisor1, divisor2, uniqueCnt1, uniqueCnt2))
        r = m;
      else
        l = m + 1;
    }

    return l;
  }

 private:
  // Returns true if we can take uniqueCnt1 integers from [1..m] to arr1 and
  // take uniqueCnt2 integers from [1..m] to arr2.
  bool isPossible(long m, long divisorLcm, int divisor1, int divisor2,
                  int uniqueCnt1, int uniqueCnt2) {
    const long cnt1 = m - m / divisor1;
    const long cnt2 = m - m / divisor2;
    const long totalCnt = m - m / divisorLcm;
    return cnt1 >= uniqueCnt1 && cnt2 >= uniqueCnt2 &&
           totalCnt >= uniqueCnt1 + uniqueCnt2;
  }
};
/* code provided by PROGIEZ */

2513. Minimize the Maximum of Two Arrays LeetCode Solution in Java

class Solution {
  public int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
    final long divisorLcm = lcm(divisor1, divisor2);
    long l = 0;
    long r = Integer.MAX_VALUE;

    while (l < r) {
      final long m = (l + r) / 2;
      if (isPossible(m, divisorLcm, divisor1, divisor2, uniqueCnt1, uniqueCnt2))
        r = m;
      else
        l = m + 1;
    }

    return (int) l;
  }

  // Returns true if we can take uniqueCnt1 integers from [1..m] to arr1 and
  // take uniqueCnt2 integers from [1..m] to arr2.
  private boolean isPossible(long m, long divisorLcm, int divisor1, int divisor2, int uniqueCnt1,
                             int uniqueCnt2) {
    final long cnt1 = m - m / divisor1;
    final long cnt2 = m - m / divisor2;
    final long totalCnt = m - m / divisorLcm;
    return cnt1 >= uniqueCnt1 && cnt2 >= uniqueCnt2 && totalCnt >= uniqueCnt1 + uniqueCnt2;
  }

  private long gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
  }

  private long lcm(int a, int b) {
    return a * (b / gcd(a, b));
  }
}
// code provided by PROGIEZ

2513. Minimize the Maximum of Two Arrays LeetCode Solution in Python

class Solution:
  def minimizeSet(
      self,
      divisor1: int,
      divisor2: int,
      uniqueCnt1: int,
      uniqueCnt2: int,
  ) -> int:
    divisorLcm = math.lcm(divisor1, divisor2)
    l = 0
    r = 2**31 - 1

    def isPossible(m: int) -> bool:
      """
      Returns True if we can take uniqueCnt1 integers from [1..m] to arr1 and
      take uniqueCnt2 integers from [1..m] to arr2.
      """
      cnt1 = m - m // divisor1
      cnt2 = m - m // divisor2
      totalCnt = m - m // divisorLcm
      return (cnt1 >= uniqueCnt1 and
              cnt2 >= uniqueCnt2 and
              totalCnt >= uniqueCnt1 + uniqueCnt2)

    while l < r:
      m = (l + r) // 2
      if isPossible(m):
        r = m
      else:
        l = m + 1

    return l
 # code by PROGIEZ