Minimize the Maximum of Two Arrays

Med

#2293Time: 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`.1 company

Patterns

Math Number Theory

Algorithms

Binary Search

Companies

Goldman Sachs

Prompt

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 <= 10⁵
1 <= uniqueCnt1, uniqueCnt2 < 10⁹
2 <= uniqueCnt1 + uniqueCnt2 <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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:

There must be at least uniqueCnt1 numbers for arr1.
There must be at least uniqueCnt2 numbers for arr2.
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).

1class Solution {2    public int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {3        long val = 1;4        long lcm = lcm((long)divisor1, (long)divisor2);5        while (true) {6            long can_fill_1 = val - val / divisor1;7            long can_fill_2 = val - val / divisor2;8            long can_fill_both = val - val / lcm;9            if (can_fill_1 >= uniqueCnt1 && can_fill_2 >= uniqueCnt2 && can_fill_both >= (long)uniqueCnt1 + uniqueCnt2) {10                return (int) val;11            }12            val++;13        }14    }15 16    private long gcd(long a, long b) {17        while (b != 0) {18            long temp = b;19            b = a % b;20            a = temp;21        }22        return a;23    }24 25    private long lcm(long a, long b) {26        if (a == 0 || b == 0) return 0;27        return (a / gcd(a, b)) * b;28    }29}

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.

Complexity

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`.

Trade-offs

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.

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.

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.

Walkthrough

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:

x - floor(x / divisor1) >= uniqueCnt1
x - floor(x / divisor2) >= uniqueCnt2
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.

1class Solution {2    public int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {3        long low = 1;4        // A safe upper bound. The sum of counts is at most 10^9.5        // In the worst case (e.g., divisor=2), we might need twice the numbers.6        // 4 * 10^9 is a very safe upper bound.7        long high = 4_000_000_000L; 8        long ans = high;9 10        long lcm = lcm((long)divisor1, (long)divisor2);11 12        while (low <= high) {13            long mid = low + (high - low) / 2;14            15            // Numbers not divisible by divisor116            long notDivisibleBy1 = mid - mid / divisor1;17            // Numbers not divisible by divisor218            long notDivisibleBy2 = mid - mid / divisor2;19            // Numbers not divisible by either (i.e., not divisible by lcm)20            long notDivisibleByBoth = mid - mid / lcm;21 22            if (notDivisibleBy1 >= uniqueCnt1 && 23                notDivisibleBy2 >= uniqueCnt2 &&24                notDivisibleByBoth >= (long)uniqueCnt1 + uniqueCnt2) {25                ans = mid;26                high = mid - 1;27            } else {28                low = mid + 1;29            }30        }31        return (int) ans;32    }33 34    private long gcd(long a, long b) {35        while (b != 0) {36            long temp = b;37            b = a % b;38            a = temp;39        }40        return a;41    }42 43    private long lcm(long a, long b) {44        if (a == 0 || b == 0) return 0;45        // (a * b) can overflow, so divide first46        return (a / gcd(a, b)) * b;47    }48}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {4    long divisor = lcm(divisor1, divisor2);5    long left = 1, right = 10000000000L;6    while (left < right) {7      long mid = (left + right) >> 1;8      long cnt1 = mid / divisor1 * (divisor1 - 1) + mid % divisor1;9      long cnt2 = mid / divisor2 * (divisor2 - 1) + mid % divisor2;10      long cnt = mid / divisor * (divisor - 1) + mid % divisor;11      if (cnt1 >= uniqueCnt1 && cnt2 >= uniqueCnt2 &&12          cnt >= uniqueCnt1 + uniqueCnt2) {13        right = mid;14      } else {15        left = mid + 1;16      }17    }18    return (int)left;19  }20private21  long lcm(int a, int b) { return (long)a * b / gcd(a, b); }22private23  int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }24}

1class Solution {2public:3  int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {4    long left = 1, right = 1e10;5    long divisor = lcm((long)divisor1, (long)divisor2);6    while (left < right) {7      long mid = (left + right) >> 1;8      long cnt1 = mid / divisor1 * (divisor1 - 1) + mid % divisor1;9      long cnt2 = mid / divisor2 * (divisor2 - 1) + mid % divisor2;10      long cnt = mid / divisor * (divisor - 1) + mid % divisor;11      if (cnt1 >= uniqueCnt1 && cnt2 >= uniqueCnt2 &&12          cnt >= uniqueCnt1 + uniqueCnt2) {13        right = mid;14      } else {15        left = mid + 1;16      }17    }18    return left;19  }20};

1class Solution:2    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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem