Minimize the Maximum of Two Arrays — Problem & Solution
Minimize the Maximum of Two Arrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Minimize the Maximum of Two Arrays is a medium coding problem on math, binary search and number theory, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Math, Binary Search, Number Theory
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Fill two initially empty arrays arr1 and arr2 with positive integers so that:
arr1holdsuniqueCnt1distinct integers, none of them divisible bydivisor1;arr2holdsuniqueCnt2distinct integers, none of them divisible bydivisor2;- no integer appears in both arrays.
Return the smallest possible value of the largest integer used in either array.
Example 1
Input: divisor1 = 2, divisor2 = 3, uniqueCnt1 = 2, uniqueCnt2 = 2
Output: 4
Explanation: arr1 = [1, 3] (odd numbers) and arr2 = [2, 4] (not multiples of 3).
Example 2
Input: divisor1 = 3, divisor2 = 5, uniqueCnt1 = 2, uniqueCnt2 = 1
Output: 3
Explanation: arr1 = [1, 2], arr2 = [3].
Example 3
Input: divisor1 = 2, divisor2 = 2, uniqueCnt1 = 500000000, uniqueCnt2 = 500000000
Output: 1999999999
Explanation: Both arrays need odd numbers, 10^9 of them in total.
Constraints
2 <= divisor1, divisor2 <= 10^51 <= uniqueCnt1, uniqueCnt2 < 10^92 <= uniqueCnt1 + uniqueCnt2 <= 10^9
Hints for Minimize the Maximum of Two Arrays
Hint 1
If the arrays can be filled using numbers up to
x, they can also be filled up tox + 1— so binary search onx.Hint 2
Among
1..x:x - x/divisor1numbers are allowed inarr1,x - x/divisor2inarr2, andx - x/lcmin at least one of them.Hint 3
xis enough exactly when all three counts reachuniqueCnt1,uniqueCnt2anduniqueCnt1 + uniqueCnt2respectively.
How to solve Minimize the Maximum of Two Arrays
Feasibility is monotone in the largest allowed value x, and it reduces to three counting inequalities. Binary search for the smallest x that satisfies all three.
Approach
- Let
L = lcm(divisor1, divisor2) = divisor1 / gcd · divisor2(up to 10^10, so use 64 bits). - For a candidate
x, requirex - floor(x/divisor1) >= uniqueCnt1,x - floor(x/divisor2) >= uniqueCnt2andx - floor(x/L) >= uniqueCnt1 + uniqueCnt2. - Binary search
xover[1, 2·10^9]for the smallest value meeting all three.
Why it works
Split 1..x into four groups: multiples of divisor2 only (usable only by arr1), multiples of divisor1 only (only by arr2), multiples of neither (either array) and multiples of both (neither). arr1 takes what it can from its private group and the rest from the shared one, arr2 likewise, so a filling exists exactly when each array has enough candidates on its own and both together have enough non-multiples of L — the three inequalities. Each count grows with x, so feasibility is monotone and binary search is valid. The answer never exceeds 2·10^9 - 1 (the worst case is both divisors 2).
Complexity
- Time —
O(log(2·10^9)) - Space —
O(1)
Pitfalls
- Checking only the two per-array conditions ignores that the arrays compete for the same numbers.
lcmcan reach 10^10 anduniqueCnt1 + uniqueCnt2is near 10^9 — keep the arithmetic in 64 bits.- Use
lcm, notdivisor1 · divisor2, when the divisors share a factor (e.g. 2 and 4).
Reference solution
Python
import math
def minimizeSet(divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:
lcm = divisor1 // math.gcd(divisor1, divisor2) * divisor2
lo, hi = 1, 2 * 10 ** 9
while lo < hi:
mid = (lo + hi) // 2
if (mid - mid // divisor1 >= uniqueCnt1 and mid - mid // divisor2 >= uniqueCnt2
and mid - mid // lcm >= uniqueCnt1 + uniqueCnt2):
hi = mid
else:
lo = mid + 1
return loJava
public static int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
long a = divisor1, b = divisor2;
while (b != 0) { long t = a % b; a = b; b = t; }
long lcm = divisor1 / a * divisor2;
long need = (long) uniqueCnt1 + uniqueCnt2;
long lo = 1, hi = 2000000000L;
while (lo < hi) {
long mid = (lo + hi) / 2;
if (mid - mid / divisor1 >= uniqueCnt1 && mid - mid / divisor2 >= uniqueCnt2 && mid - mid / lcm >= need) hi = mid;
else lo = mid + 1;
}
return (int) lo;
}C++
int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
long long a = divisor1, b = divisor2;
while (b != 0) { long long t = a % b; a = b; b = t; }
long long lcm = divisor1 / a * divisor2;
long long need = (long long) uniqueCnt1 + uniqueCnt2;
long long lo = 1, hi = 2000000000LL;
while (lo < hi) {
long long mid = (lo + hi) / 2;
if (mid - mid / divisor1 >= uniqueCnt1 && mid - mid / divisor2 >= uniqueCnt2 && mid - mid / lcm >= need) hi = mid;
else lo = mid + 1;
}
return (int) lo;
}JavaScript
var minimizeSet = function(divisor1, divisor2, uniqueCnt1, uniqueCnt2) {
var a = divisor1, b = divisor2;
while (b !== 0) { var t = a % b; a = b; b = t; }
var lcm = divisor1 / a * divisor2;
var lo = 1, hi = 2000000000;
while (lo < hi) {
var mid = Math.floor((lo + hi) / 2);
var ok = mid - Math.floor(mid / divisor1) >= uniqueCnt1 &&
mid - Math.floor(mid / divisor2) >= uniqueCnt2 &&
mid - Math.floor(mid / lcm) >= uniqueCnt1 + uniqueCnt2;
if (ok) hi = mid; else lo = mid + 1;
}
return lo;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 337 math problems · the whole catalogue
Learn the technique: Binary Search