Minimize the Maximum of Two Arrays
MedPrompt
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:
arr1containsuniqueCnt1distinct positive integers, each of which is not divisible bydivisor1.arr2containsuniqueCnt2distinct positive integers, each of which is not divisible bydivisor2.- No integer is present in both
arr1andarr2.
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 <= 1051 <= uniqueCnt1, uniqueCnt2 < 1092 <= uniqueCnt1 + uniqueCnt2 <= 109
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 usesgcdto find the least common multiple. Uselongto avoid overflow. - Start a loop with a counter
xinitialized to 1. - In each iteration, check if
xis 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, andcan_fill_both >= uniqueCnt1 + uniqueCnt2, thenxis the minimum possible maximum. Returnx.
- a. Calculate
- If the conditions are not met, increment
xand 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 bydivisor1) isx - floor(x / divisor1). - The count of numbers available for
arr2(not divisible bydivisor2) isx - 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 isx - floor(x / lcm(divisor1, divisor2)).
For x to be a valid candidate, three conditions must be met:
- There must be at least
uniqueCnt1numbers forarr1. - There must be at least
uniqueCnt2numbers forarr2. - There must be at least
uniqueCnt1 + uniqueCnt2numbers 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).
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.
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.
Solutions
Solution
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); }}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.