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 <= 109This 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.
C++
Java
C
C#
JavaScript
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.
C++
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. |
Minimize Maximum of Array - Leetcode 2439 - Python • NeetCodeIO • 25,249 views views
Watch 9 more video solutions →Practice Minimize the Maximum of Two Arrays with our built-in code editor and test cases.
Practice on FleetCode