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 <= 109The key idea in #2513 Minimize the Maximum of Two Arrays is to construct two arrays under divisibility constraints while keeping the maximum chosen number as small as possible. Instead of directly building the arrays, we can reframe the problem as a decision question: for a given maximum value x, can we pick enough numbers that satisfy the required conditions?
This observation allows us to apply binary search on the answer. For each candidate value x, count how many integers in the range [1, x] are not divisible by the specified divisors. Using number theory, particularly LCM, we can determine how many numbers are exclusively valid for each array and how many can be shared. If the counts satisfy the required sizes of both arrays, the value is feasible.
By shrinking the search space using binary search and validating feasibility with arithmetic counts, we efficiently find the smallest possible maximum value. This approach avoids explicit construction of arrays and keeps the solution scalable.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Binary Search with Divisibility Counting | O(log N) | O(1) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Use binary search to find smallest maximum element.
Add numbers divisible by x in nums2 and vice versa.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Key concepts include divisibility counting and least common multiple (LCM). These help determine how many numbers are divisible by certain divisors and avoid double-counting when evaluating constraints.
Problems combining binary search with number theory are common in technical interviews at companies like FAANG. This question tests mathematical reasoning, optimization thinking, and the ability to transform a construction problem into a feasibility check.
Binary search is used because the problem asks for the smallest possible maximum value. Since feasibility is monotonic (if a value works, larger values will also work), binary search efficiently finds the minimum valid result.
The optimal approach uses binary search on the answer combined with number theory. For each candidate maximum value, we count valid numbers using divisibility rules and LCM to check if both arrays can be formed.