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.
This approach leverages binary search to efficiently find the smallest possible maximum value that satisfies all the conditions. The main idea is to binary search on the range of possible maximum integers and check if a given maximum integer can accommodate the required distinct numbers in both arrays without violating the divisibility and uniqueness constraints.
We conduct a binary search over the potential maximum integers. For each mid point, we calculate how many numbers are available for both arrays:
This Python solution implements the binary search approach. We define a helper function `enough` which checks if a given maximum integer 'x' can satisfy the conditions for both arrays given the constraints.
The binary search is performed over the interval [1, 2 * (uniqueCnt1 + uniqueCnt2)], adjusting the search range according to the outcome of the 'enough' function.
This ensures optimal determination of the minimum maximum integer efficiently.
Time Complexity: O(log(max) * log(max(a, b))), where max is the upper bound of our search range and 'a', 'b' are the divisors.
Space Complexity: O(1) as only a constant amount of space is used.
This approach utilizes the Least Common Multiple (LCM) to determine integers that are not useful for any of the two arrays and applies arithmetic operations to calculate the valid count of numbers that can be distinctly placed in either array without causing violations.
Consider inclusion-exclusion principles, counting valid numbers not divisible by each divisor, and ensuring there is no overlap between chosen numbers for both arrays.
By iterating over potential ranges of numbers, use mathematical deduction to distribute numbers optimally.
This Python solution leverages mathematical principles and computes available lengths for each array after eliminating numbers divisible by each divisor. The algorithm ensures numbers are optimally assigned to either array.
Time Complexity: O(log(max_num) + log(min(divisor1, divisor2))) due to binary search and gcd calculations.
Space Complexity: O(1) since we use constant auxiliary space.
| Approach | Complexity |
|---|---|
| Approach 1: Binary Search on the Minimum Maximum Value | Time Complexity: O(log(max) * log(max(a, b))), where max is the upper bound of our search range and 'a', 'b' are the divisors. |
| Approach 2: LCM-based Counting and Mathematical Deduction | Time Complexity: O(log(max_num) + log(min(divisor1, divisor2))) due to binary search and gcd calculations. |
| Default Approach | — |
| 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 |
Leetcode Biweekly Contest 94 | 2513 : Minimize the Maximum of Two Arrays Solution | Newton School • Coding Community | Newton School • 5,438 views views
Watch 8 more video solutions →Practice Minimize the Maximum of Two Arrays with our built-in code editor and test cases.
Practice on FleetCode