Watch 9 video solutions for Minimize the Maximum of Two Arrays, a medium level problem involving Math, Binary Search, Number Theory. This walkthrough by Coding Community | Newton School has 5,438 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.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 <= 1051 <= uniqueCnt1, uniqueCnt2 < 1092 <= uniqueCnt1 + uniqueCnt2 <= 109Problem Overview: You must construct two arrays of sizes uniqueCnt1 and uniqueCnt2. Numbers in the first array cannot be divisible by divisor1, and numbers in the second cannot be divisible by divisor2. All numbers must be distinct. The goal is to minimize the maximum value used across both arrays.
Approach 1: Binary Search on the Minimum Maximum Value (O(log R) time, O(1) space)
The key observation: instead of constructing arrays directly, search for the smallest value x such that numbers from 1..x can satisfy both arrays. Use binary search on the answer space because feasibility is monotonic. For a candidate x, count how many numbers are not divisible by divisor1, not divisible by divisor2, and not divisible by either. Use inclusion–exclusion with lcm(divisor1, divisor2) to compute overlaps. Check three constraints: enough numbers for array1, enough for array2, and enough total numbers not divisible by both divisors combined to satisfy uniqueCnt1 + uniqueCnt2. If the counts work, shrink the search range; otherwise increase x. This approach converts a combinatorial construction problem into a fast counting check using math and number theory.
Approach 2: LCM-based Counting and Mathematical Deduction (O(log R) time, O(1) space)
This approach focuses on categorizing numbers based on divisibility relationships. Numbers fall into three useful groups: divisible only by divisor1, divisible only by divisor2, and divisible by neither. The overlap is determined using lcm(divisor1, divisor2). During the search for the minimal maximum value, compute how many candidates are safe for array1 (x - x/divisor1) and array2 (x - x/divisor2). Then verify the shared pool of numbers not divisible by either divisor (x - x/divisor1 - x/divisor2 + x/lcm) can cover any remaining requirement after assigning exclusive numbers. This mathematical counting removes any need for simulation or data structures and keeps the feasibility check constant time.
Recommended for interviews: The binary search formulation is what interviewers typically expect. It demonstrates recognition of monotonic search space plus correct use of LCM and inclusion–exclusion. Explaining the counting logic clearly matters more than the code itself. A brute-force construction would be far too slow for large ranges, while the binary search + math approach scales efficiently and shows strong algorithmic reasoning.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Search on Maximum Value | O(log R) | O(1) | General case; most intuitive and commonly used interview solution |
| LCM-based Mathematical Counting | O(log R) | O(1) | When you want a pure mathematical feasibility check using inclusion–exclusion |