# Minimize the Maximum of Two Arrays
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimize-the-maximum-of-two-arrays)
Canonical: https://scaleengineer.com/dsa/problems/minimize-the-maximum-of-two-arrays
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Companies:** [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs)
---
## Problem
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`

# Approaches
## Brute Force (Linear Search)
This approach involves checking every possible integer `x` starting from 1, to see if it can be the maximum value in the arrays. The first value `x` that satisfies all the conditions is the minimum possible maximum, and we return it.
**Time:** O(ANS * log(D)), where `ANS` is the final answer and `D` is `min(divisor1, divisor2)`. The loop runs up to `ANS` times, and inside the loop, calculating LCM involves a GCD computation which takes logarithmic time. Given `ANS` can be very large, this is not feasible. · **Space:** O(1), as we only use a few variables to store counts and the current value of `x`.
**Pros:** Simple to understand and implement.; Guaranteed to find the correct answer if it runs to completion.
**Cons:** Extremely inefficient. The answer can be as large as `2 * 10^9`, leading to a very high number of iterations.; Will result in a "Time Limit Exceeded" (TLE) error on platforms with typical time constraints.
### Explanation
To check if a given integer `x` is a valid maximum, we need to determine if we can select `uniqueCnt1` and `uniqueCnt2` distinct integers from the range `[1, x]` that satisfy the divisibility constraints.
Let's analyze the number of available integers up to `x`:
- The count of numbers available for `arr1` (not divisible by `divisor1`) is `x - floor(x / divisor1)`.
- The count of numbers available for `arr2` (not divisible by `divisor2`) is `x - floor(x / divisor2)`.
- The count of numbers available for either array is found using the Principle of Inclusion-Exclusion. The total numbers available for both arrays combined are those not divisible by `lcm(divisor1, divisor2)`. The count is `x - floor(x / lcm(divisor1, divisor2))`.

For `x` to be a valid candidate, three conditions must be met:
1. There must be at least `uniqueCnt1` numbers for `arr1`.
2. There must be at least `uniqueCnt2` numbers for `arr2`.
3. There must be at least `uniqueCnt1 + uniqueCnt2` numbers in total for both arrays combined.

The algorithm iterates `x` from 1 upwards, and for each `x`, it checks these three conditions. The first `x` to satisfy them is the answer.
We need a helper function for the Greatest Common Divisor (GCD) to compute the Least Common Multiple (LCM), as `lcm(a, b) = (a * b) / gcd(a, b)`.
```java
class Solution {
    public int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
        long val = 1;
        long lcm = lcm((long)divisor1, (long)divisor2);
        while (true) {
            long can_fill_1 = val - val / divisor1;
            long can_fill_2 = val - val / divisor2;
            long can_fill_both = val - val / lcm;
            if (can_fill_1 >= uniqueCnt1 && can_fill_2 >= uniqueCnt2 && can_fill_both >= (long)uniqueCnt1 + uniqueCnt2) {
                return (int) val;
            }
            val++;
        }
    }

    private long gcd(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    private long lcm(long a, long b) {
        if (a == 0 || b == 0) return 0;
        return (a / gcd(a, b)) * b;
    }
}
```
Note: The `lcm` calculation `a * b` can overflow standard integers, so using `long` is crucial. The loop `while(true)` will eventually find the answer, but it's too slow for the given constraints.
### Algorithm
- Implement a helper function `gcd(a, b)` to find the greatest common divisor of two numbers.
- Implement a helper function `lcm(a, b)` that uses `gcd` to find the least common multiple. Use `long` to avoid overflow.
- Start a loop with a counter `x` initialized to 1.
- In each iteration, check if `x` is a valid maximum:
  - a. Calculate `can_fill_1 = x - x / divisor1`.
  - b. Calculate `can_fill_2 = x - x / divisor2`.
  - c. Calculate `can_fill_both = x - x / lcm(divisor1, divisor2)`.
  - d. If `can_fill_1 >= uniqueCnt1`, `can_fill_2 >= uniqueCnt2`, and `can_fill_both >= uniqueCnt1 + uniqueCnt2`, then `x` is the minimum possible maximum. Return `x`.
- If the conditions are not met, increment `x` and continue the loop.

## Binary Search on the Answer
This approach leverages the monotonic nature of the problem. If an integer `x` is a valid maximum, any integer greater than `x` is also a valid maximum. This property allows us to use binary search to find the minimum valid `x` efficiently. We define a search space for the answer and repeatedly narrow it down until we find the smallest possible value.
**Time:** O(log(N)), where `N` is the size of the search space (e.g., `4 * 10^9`). The `gcd` calculation inside the `lcm` function takes `O(log(D))` where `D` is `min(divisor1, divisor2)`, but this is done only once before the loop. Each step of the binary search takes constant time. · **Space:** O(1), as it only requires a few variables to store the search boundaries and the answer.
**Pros:** Highly efficient and fast, capable of handling large constraints.; The logic is sound and based on a standard algorithmic pattern (binary search on the answer).
**Cons:** Slightly more complex to conceptualize than a linear search.; Requires careful handling of potential integer overflows by using `long` for intermediate calculations, especially for LCM and the search range.
### Explanation
The core idea is to create a function, let's call it `isPossible(x)`, that returns `true` if `x` can be the maximum value in the arrays and `false` otherwise. As explained in the brute-force approach, `isPossible(x)` is true if and only if the following three conditions hold:
1.  `x - floor(x / divisor1) >= uniqueCnt1`
2.  `x - floor(x / divisor2) >= uniqueCnt2`
3.  `x - floor(x / lcm(divisor1, divisor2)) >= uniqueCnt1 + uniqueCnt2`

Since `isPossible(x)` is monotonic (if it's true for `x`, it's true for all `y > x`), we can apply binary search. We need to define a search range `[low, high]`.
- `low`: A lower bound for the answer can be 1.
- `high`: An upper bound needs to be large enough. Since `uniqueCnt1 + uniqueCnt2` can be up to `10^9`, and in the worst case (e.g., `divisor1=2`), we might need about twice that many numbers, a safe upper bound is `2 * (uniqueCnt1 + uniqueCnt2)` or simply a large number like `4 * 10^9`.

The binary search proceeds as follows: pick a `mid` value in the `[low, high]` range. If `isPossible(mid)` is true, it means `mid` could be our answer, but there might be a smaller valid answer, so we search in `[low, mid - 1]`. If `isPossible(mid)` is false, `mid` is too small, so we must search in `[mid + 1, high]`. We continue this until `low` exceeds `high`, and the smallest `mid` for which `isPossible` was true is our answer.

```java
class Solution {
    public int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
        long low = 1;
        // A safe upper bound. The sum of counts is at most 10^9.
        // In the worst case (e.g., divisor=2), we might need twice the numbers.
        // 4 * 10^9 is a very safe upper bound.
        long high = 4_000_000_000L; 
        long ans = high;

        long lcm = lcm((long)divisor1, (long)divisor2);

        while (low <= high) {
            long mid = low + (high - low) / 2;
            
            // Numbers not divisible by divisor1
            long notDivisibleBy1 = mid - mid / divisor1;
            // Numbers not divisible by divisor2
            long notDivisibleBy2 = mid - mid / divisor2;
            // Numbers not divisible by either (i.e., not divisible by lcm)
            long notDivisibleByBoth = mid - mid / lcm;

            if (notDivisibleBy1 >= uniqueCnt1 && 
                notDivisibleBy2 >= uniqueCnt2 &&
                notDivisibleByBoth >= (long)uniqueCnt1 + uniqueCnt2) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return (int) ans;
    }

    private long gcd(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    private long lcm(long a, long b) {
        if (a == 0 || b == 0) return 0;
        // (a * b) can overflow, so divide first
        return (a / gcd(a, b)) * b;
    }
}
```
### Algorithm
- Define the search range for the answer. `low = 1`, `high = 4 * 10^9` (a safe upper bound).
- Calculate `lcm = lcm(divisor1, divisor2)`. Use 64-bit integers (`long`) to prevent overflow during calculation.
- Start a `while` loop that continues as long as `low <= high`.
- Inside the loop, calculate `mid = low + (high - low) / 2`.
- Check if `mid` is a possible answer by verifying the three conditions:
  - a. `mid - mid / divisor1 >= uniqueCnt1`
  - b. `mid - mid / divisor2 >= uniqueCnt2`
  - c. `mid - mid / lcm >= uniqueCnt1 + uniqueCnt2`
- If all conditions are true, `mid` is a potential answer. Store it and try to find a smaller one by setting `high = mid - 1`.
- If any condition is false, `mid` is too small. Search for a larger value by setting `low = mid + 1`.
- After the loop terminates, the last stored potential answer is the minimum possible one. Return it.

# Solutions
### Java

```java
class Solution {
public
  int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
    long divisor = lcm(divisor1, divisor2);
    long left = 1, right = 10000000000L;
    while (left < right) {
      long mid = (left + right) >> 1;
      long cnt1 = mid / divisor1 * (divisor1 - 1) + mid % divisor1;
      long cnt2 = mid / divisor2 * (divisor2 - 1) + mid % divisor2;
      long cnt = mid / divisor * (divisor - 1) + mid % divisor;
      if (cnt1 >= uniqueCnt1 && cnt2 >= uniqueCnt2 &&
          cnt >= uniqueCnt1 + uniqueCnt2) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return (int)left;
  }
private
  long lcm(int a, int b) { return (long)a * b / gcd(a, b); }
private
  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
}

```

### CPP

```cpp
class Solution {
public:
  int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
    long left = 1, right = 1e10;
    long divisor = lcm((long)divisor1, (long)divisor2);
    while (left < right) {
      long mid = (left + right) >> 1;
      long cnt1 = mid / divisor1 * (divisor1 - 1) + mid % divisor1;
      long cnt2 = mid / divisor2 * (divisor2 - 1) + mid % divisor2;
      long cnt = mid / divisor * (divisor - 1) + mid % divisor;
      if (cnt1 >= uniqueCnt1 && cnt2 >= uniqueCnt2 &&
          cnt >= uniqueCnt1 + uniqueCnt2) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
};

```

### Python

```python
class Solution:
    def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int: def f(x): cnt1 = x // divisor1 * (divisor1 - 1) + x % divisor1 cnt2 = x // divisor2 * (divisor2 - 1) + x % divisor2 cnt = x // divisor * (divisor - 1) + x % divisor return (cnt1 >= uniqueCnt1 and cnt2 >= uniqueCnt2 and cnt >= uniqueCnt1 + uniqueCnt2) divisor = lcm(divisor1, divisor2) return bisect_left(range(10 ** 10), True, key=f)

```