2513. Minimize the Maximum of Two Arrays
Problem Description
The essence of this problem is to fill two initially empty arrays arr1 and arr2 with distinct positive integers that are not divisible by respective divisors: divisor1 for arr1 and divisor2 for arr2. Additionally, we must ensure that no integer is present in both arrays. The goal is to figure out the minimum value of the maximum integer that can be present in either of the arrays while meeting the following conditions:
arr1
must containuniqueCnt1
distinct positive integers, none of which should be divisible bydivisor1
.arr2
must containuniqueCnt2
distinct positive integers, none of which should be divisible bydivisor2
.- There must not be any overlap between the integers in
arr1
andarr2
.
The challenge thus revolves around selecting numbers carefully to minimize the highest number placed in either array, all the while respecting the given divisibility rules.
Intuition
The solution to this problem can be derived using a binary search on the range of possible maximum values for the arrays. Since a binary search requires a sorted range and certain conditions to find a target, we define the conditions based on understanding how many numbers will be allowed in each array up to a certain value x
. The binary search begins with an initial range from 0 to an arbitrarily large number (in this case, 10^10), looking for the smallest x
that satisfies our conditions.
Firstly, we need a function that checks if x
can be the maximum possible integer in either array. I will define f(x)
, which calculates the count of distinct non-divisible integers up to x
for arr1
and arr2
separately, and a combined count for both arrays together. It does so by incorporating the floor division and modulo operations for each divisor as well as the lowest common multiple (LCM) of both divisors.
The intuition behind these calculations is that every divisor1
consecutive numbers, divisor1 - 1
will be admissible for arr1
since one will be divisible and thus excluded. The same logic applies to arr2
with divisor2
. For common elements to be excluded from both arrays, we consider the LCM of both divisors, as any number divisible by the LCM would be divisible by both divisor1
and divisor2
.
The function f(x)
checks whether, up to the number x
, there are at least uniqueCnt1
non-divisible numbers for arr1
, uniqueCnt2
for arr2
, and a combined uniqueCnt1 + uniqueCnt2
for both with overlap removed. If this condition holds, then x
is a candidate for the minimum possible maximum integer.
The use of bisect_left
in Python is how we do our binary search here. It essentially searches for the place where True
would be inserted in the range to keep it sorted, as per the f(x)
condition. This gives us the smallest value x
that satisfies f(x)
.
By initializing the binary search with a large enough range, we ensure that we can find a cut-off point where f(x)
transitions from False
to True
, indicating that we've found the minimum possible maximum integer for the arrays.
Learn more about Math and Binary Search patterns.
Solution Approach
The implementation of the solution utilizes several important concepts from algorithms and mathematics:
-
Least Common Multiple (LCM): Before we start the binary search, we need to find the least common multiple of the two divisors. This is crucial as we need to exclude numbers divisible by both
divisor1
anddivisor2
when counting the numbers admissible in both arrays combined. As the LCM is not provided in the solution code, it must be implemented in helper functions or use external libraries. -
Counting Function (
f
): We define a counting functionf(x)
that uses arithmetic to determine the count of distinct non-divisible integers up to a certain valuex
for each array, as well as combined. In more detail:- We calculate
cnt1
by determining how many groups ofdivisor1
can fit intox
(given byx // divisor1
) and then adding the remaining numbers (given byx % divisor1
). We exclude one number for each full group since one number will be divisible bydivisor1
. - Similarly,
cnt2
is calculated forarr2
anddivisor2
. - For the combined count
cnt
, we apply the same logic using the LCM of the two divisors since we want to exclude numbers that are disallowed in both arrays.
- We calculate
-
Binary Search Algorithm: With
bisect_left
, we are efficiently conducting a binary search. The range[0, 10**10]
is just a representation of an upper bound that we are confident is much higher than our target maximum integer. Binary search is applied by usingf(x)
as the key function forbisect_left
which allows us to find the smallest numberx
for whichf(x)
returnsTrue
, i.e., the counting function indicates that botharr1
andarr2
have their required distinct positive integers. -
Binary Search with a Custom Condition (
f
): Instead of looking for an actual value in a sorted list, as is typical with binary search, we are using the binary search to find the point at which a condition changes fromFalse
toTrue
. This binary search is abstract in the sense that it operates on the truth value off(x)
over a range of numbers.
By combining the above techniques, the solution finds the minimum possible maximum integer with the least amount of computation necessary, avoiding the need to directly generate the arrays or to iterate over large ranges of numbers, which would be inefficient.
The most crucial part of the solution is ensuring that the key function f(x)
accurately reflects the conditions we need for arr1
and arr2
. Once f(x)
is correctly defined, bisect_left
takes over to execute the binary search, taking advantage of the fact that f(x)
will be False
until it isn'tāat which point we've found our minimum maximum.
It's worth noting that mathematical intuition is key in converting the problem into one that can be solved with binary search. Specifically, understanding how to calculate the number of admissible numbers given the constraints on divisibility and ensuring the arrays remain disjoint are the fundamental subproblems addressed by the counting function f(x)
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider an example scenario to illustrate the solution approach:
Assume we have divisor1 = 2
, divisor2 = 3
, uniqueCnt1 = 2
, and uniqueCnt2 = 2
.
We need to create two arrays, arr1
and arr2
, such that:
arr1
contains two distinct integers not divisible by2
.arr2
contains two distinct integers not divisible by3
.- None of the integers are overlapping between
arr1
andarr2
.
Step-by-Step Process
-
Finding the Least Common Multiple (LCM):
- The LCM of
2
and3
is6
. We need this for counting common numbers that would be excluded from both arrays.
- The LCM of
-
Defining the Counting Function (
f
):- Let's say we are checking if
x = 7
can be the maximum integer in either array. - For
divisor1 = 2
, up tox = 7
, the numbers1, 3, 5, 7
(four numbers) are not divisible by2
. - For
divisor2 = 3
, up tox = 7
, the numbers1, 2, 4, 5, 7
(five numbers) are not divisible by3
. - For numbers up to
x = 7
that are not divisible by2
or3
(using LCM of6
), we get1, 5, 7
(three numbers).
- Let's say we are checking if
-
Applying Binary Search with Custom Condition (
f
):- Since we require at least
2
numbers for each array and to avoid overlap, we need to confirm if the combined total without overlap is at least4
. Forx = 7
, we have3
such numbers, sof(7)
isFalse
. - Using binary search, we increase
x
and check again. Let's sayx = 8
. We repeat the counting:- For
divisor1 = 2
, the numbers are1, 3, 5, 7
(still four numbers). - For
divisor2 = 3
, the numbers are1, 2, 4, 5, 7, 8
(six numbers). - Using the LCM of
6
, the numbers are1, 5, 7
(still three numbers).
- For
- Since we require at least
-
Finding the Transition Point:
- For
x = 8
,f(8)
isFalse
as we still don't have at least4
non-overlapping numbers. We proceed with the binary search. - Increment
x
and check again. Atx = 10
, we repeat the counting:- Non-divisible by
2
:1, 3, 5, 7, 9
(five numbers). - Non-divisible by
3
:1, 2, 4, 5, 7, 8, 10
(seven numbers). - Non-divisible by both (
LCM = 6
):1, 5, 7, 11
(four numbers ā11
is now included sincex = 10
).
- Non-divisible by
- Since
f(10)
isTrue
for the first time (we have at least2
numbers for each array without overlap), the binary search concludes, and we consider10
to be the smallest possible maximum integer that satisfies all conditions.
- For
Therefore, for our example with the chosen parameters, the minimum possible maximum integer that can be placed in either array while satisfying all conditions is 10
. This example demonstrates the method through which we can utilize a binary search to efficiently solve for the required parameters.
Solution Implementation
1from math import gcd
2from bisect import bisect_left
3
4class Solution:
5 def minimizeSet(self, divisor1: int, divisor2: int, unique_cnt1: int, unique_cnt2: int) -> int:
6 # Auxiliary function to determine the lowest common multiple (LCM) of two numbers
7 def lcm(a, b):
8 return a * b // gcd(a, b)
9
10 # Define the condition function that will be used with binary search
11 def condition(x: int) -> bool:
12 # Calculate the number of integers not divisible by divisor1 up to x
13 nondiv_cnt1 = x // divisor1 * (divisor1 - 1) + x % divisor1
14 # Calculate the number of integers not divisible by divisor2 up to x
15 nondiv_cnt2 = x // divisor2 * (divisor2 - 1) + x % divisor2
16 # Calculate the number of integers not divisible by the LCM of divisor1 and divisor2 up to x
17 nondiv_cnt_total = x // lcm_value * (lcm_value - 1) + x % lcm_value
18 # Check if the counted non-divisible integers meet or exceed the unique count requirements
19 return (
20 nondiv_cnt1 >= unique_cnt1 and
21 nondiv_cnt2 >= unique_cnt2 and
22 nondiv_cnt_total >= unique_cnt1 + unique_cnt2
23 )
24
25 # Calculate the least common multiple of the two divisors
26 lcm_value = lcm(divisor1, divisor2)
27
28 # Perform binary search to find the smallest integer x for which condition(x) is True
29 # The search space is assumed to be up to 10^10
30 result = bisect_left(range(10**10), True, key=condition)
31
32 return result
33
1class Solution {
2
3 // Method to minimize the set size based on provided divisors and unique count requirements
4 public int minimizeSet(int divisor1, int divisor2, int uniqueCount1, int uniqueCount2) {
5 // Calculate the least common multiple of the two divisors
6 long leastCommonMultiple = calculateLCM(divisor1, divisor2);
7
8 // Initialize search space for the minimum set size
9 long left = 1, right = 10000000000L;
10
11 // Binary search to find the minimum set size
12 while (left < right) {
13 long mid = (left + right) >> 1; // Calculate the midpoint
14
15 // Calculate the number of unique elements for divisor1 and divisor2,
16 // and both combined in the range [1, mid]
17 long count1 = mid / divisor1 * (divisor1 - 1) + mid % divisor1;
18 long count2 = mid / divisor2 * (divisor2 - 1) + mid % divisor2;
19 long combinedCount = mid / leastCommonMultiple * (leastCommonMultiple - 1) + mid % leastCommonMultiple;
20
21 // Check if the current midpoint meets the unique count requirements
22 if (count1 >= uniqueCount1 && count2 >= uniqueCount2 && combinedCount >= uniqueCount1 + uniqueCount2) {
23 right = mid; // Midpoint is valid, try to find smaller number
24 } else {
25 left = mid + 1; // Midpoint is too small, increase lower bound
26 }
27 }
28
29 // Cast to int as per the problem constraints, the resulting set size is safe to be within integer range
30 return (int) left;
31 }
32
33 // Helper method to calculate the least common multiple (LCM) of two numbers
34 private long calculateLCM(int a, int b) {
35 return (long) a * b / calculateGCD(a, b);
36 }
37
38 // Helper method to calculate the greatest common divisor (GCD) of two numbers using Euclid's algorithm
39 private int calculateGCD(int a, int b) {
40 return b == 0 ? a : calculateGCD(b, a % b);
41 }
42}
43
1#include <algorithm> // For std::lcm
2
3class Solution {
4public:
5 int minimizeSet(int divisor1, int divisor2, int uniqueCount1, int uniqueCount2) {
6 long left = 1, right = 1e10; // Define search space for binary search
7 long leastCommonMultiple = std::lcm(static_cast<long>(divisor1), static_cast<long>(divisor2)); // Compute LCM
8
9 // Perform a binary search to find the smallest number that satisfies the conditions.
10 while (left < right) {
11 long mid = (left + right) / 2; // Find the midpoint of the current search space
12
13 // Calculate how many unique numbers exist for 'mid' when considering divisor1 and divisor2 separately
14 long count1 = mid / divisor1 * (divisor1 - 1) + mid % divisor1;
15 long count2 = mid / divisor2 * (divisor2 - 1) + mid % divisor2;
16
17 // Calculate the unique count for both divisors when they are combined
18 long combinedCount = mid / leastCommonMultiple * (leastCommonMultiple - 1) + mid % leastCommonMultiple;
19
20 // Check if 'mid' satisfies all of the minimum requirements for unique numbers for both divisors
21 if (count1 >= uniqueCount1 && count2 >= uniqueCount2 && combinedCount >= uniqueCount1 + uniqueCount2) {
22 // If so, narrow the search to the lower half, including 'mid'
23 right = mid;
24 } else {
25 // Otherwise, narrow the search to the upper half, excluding 'mid'
26 left = mid + 1;
27 }
28 }
29
30 // After exiting the loop, 'left' will be the minimum number that satisfies all requirements.
31 return left;
32 }
33};
34
1function lcm(a: number, b: number): number {
2 // Helper function to find the least common multiple (LCM) using the greatest common divisor (GCD) method
3 let gcd = function gcd(a: number, b: number): number {
4 return b ? gcd(b, a % b) : a;
5 };
6 // Formula for LCM: |a * b| / gcd(a, b)
7 return Math.abs(a * b) / gcd(a, b);
8}
9
10function minimizeSet(divisor1: number, divisor2: number, uniqueCount1: number, uniqueCount2: number): number {
11 let left: number = 1, right: number = 1e10; // Define search space for binary search
12 let leastCommonMultiple: number = lcm(divisor1, divisor2); // Compute LCM using the helper function
13
14 // Perform a binary search to find the smallest number that satisfies the conditions.
15 while (left < right) {
16 let mid: number = Math.floor((left + right) / 2); // Find the midpoint of the current search space
17
18 // Calculate how many unique numbers exist for 'mid' when considering divisor1 and divisor2 separately
19 let count1: number = Math.floor(mid / divisor1) * (divisor1 - 1) + mid % divisor1;
20 let count2: number = Math.floor(mid / divisor2) * (divisor2 - 1) + mid % divisor2;
21
22 // Calculate the unique count for both divisors when they are combined
23 let combinedCount: number = Math.floor(mid / leastCommonMultiple) * (leastCommonMultiple - 1) + mid % leastCommonMultiple;
24
25 // Check if 'mid' satisfies all of the minimum requirements for unique numbers for both divisors
26 if (count1 >= uniqueCount1 && count2 >= uniqueCount2 && combinedCount >= uniqueCount1 + uniqueCount2) {
27 // If so, narrow the search to the lower half, including 'mid'
28 right = mid;
29 } else {
30 // Otherwise, narrow the search to the upper half, excluding 'mid'
31 left = mid + 1;
32 }
33 }
34
35 // After exiting the loop, 'left' will be the minimum number that satisfies all requirements.
36 return left;
37}
38
Time and Space Complexity
The given Python code aims to find the minimum number x
that satisfies certain divisibility conditions. The code is expected to use the bisect_left
function from the bisect
module to perform a binary search for the smallest value of x
where function f(x)
returns True
. Unfortunately, the provided code contains errors and it's incomplete (there's a reference to an undefined variable divisor
inside the f(x)
function). Assuming these issues were fixed and the lcm
function (least common multiple) and bisect_left
were correctly implemented, we can proceed with the time and space complexity analysis.
Time complexity:
-
bisect_left
: The binary search implemented bybisect_left
has a time complexity ofO(log N)
, whereN
is the size of the range. In this case,N
is set to10**10
, which is a constant, so thebisect_left
call alone would have a complexity ofO(log 10**10)
which simplifies toO(log 10)
due to the base not being specified in the Big O notation. -
Function
f
: This function is called bybisect_left
at each step of the binary search. The operations inside functionf
are performed in constant time (basic arithmetic operations) and do not depend on the size of the input.
Combining the two above, we get O(log 10)
multiplied by the time complexity of f
, which is O(1)
, resulting in O(log 10)
. However, the improper references in the f(x)
function can alter this analysis if, for example, computing the lcm
has a non-constant complexity.
Space complexity:
-
bisect_left
: The space complexity of the binary search isO(1)
since it doesn't allocate any additional space that grows with the input. -
LCM computation: If the
lcm
is computed each timef(x)
is called, and the computation oflcm
is not inO(1)
space, this would affect the space complexity. If thelcm
is computed once and used multiple times with a constant space complexity, the space complexity will remainO(1)
. -
Function
f
: Since the functionf
only uses a fixed number of variables and does not use any data structures that scale with the size of the input, its space complexity isO(1)
.
Considering all the above, the overall space complexity of the code is O(1)
, provided the computationally-intensive tasks such as finding the least common multiple have constant space complexity and are computed outside of the f(x)
function or are otherwise cached.
It's important to note that the presence of the range(10**10)
in the bisect_left
function does not impact space complexity since range
in Python 3 creates a range object that does not generate all numbers in memory but computes them on-the-fly.
Learn more about how to find time and space complexity quickly using problem constraints.
Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!