Minimize the Maximum of Two Arrays

#1473 Most AskedMedium

Minimize the Maximum of Two Arrays #1473 Most Asked

Medium

9 views

Topics:

Binary Search

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.
No integer is present in both 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 <= 10⁵
1 <= uniqueCnt1, uniqueCnt2 < 10⁹
2 <= uniqueCnt1 + uniqueCnt2 <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for `divisor1`, `divisor2`, `uniqueCnt1`, and `uniqueCnt2`? Are they always positive integers?
Can `uniqueCnt1` or `uniqueCnt2` be zero?
If it's impossible to satisfy the conditions (e.g., `uniqueCnt1` + `uniqueCnt2` is greater than the total possible values), what value should I return?
Are `divisor1` and `divisor2` guaranteed to be distinct?
Could you provide a small example to illustrate the expected behavior?

Brute Force Solution

Approach

The brute force method for this problem involves trying out every possible maximum value. We check if it is possible to construct the two arrays using that maximum value, given the rules for divisibility by the provided numbers.

Here's how the algorithm would work step-by-step:

Start by guessing the smallest possible maximum value, which is 1.
See if you can build the first array, making sure all its required numbers are not divisible by the first special number. Also, check if the number of integers that meet the criteria are greater or equal to the number requested for the array.
Then, see if you can build the second array, making sure all its required numbers are not divisible by the second special number. Also, check if the number of integers that meet the criteria are greater or equal to the number requested for the array.
If both arrays can be successfully built without sharing any numbers, the current maximum value is a potential solution.
If you cannot build either of the arrays with that maximum, or if the two arrays have shared numbers, then increment the maximum value by one, and try again.
Repeat this process until you find the smallest maximum value that allows you to successfully build both arrays according to the rules.

Code Implementation

def minimize_maximum_brute_force(
    array_one_count,
    array_two_count,
    divisor_one,
    divisor_two
):
    maximum_value = 1

    while True:
        # Check if we can construct array one
        count_one_valid_numbers = 0

        # Check if we can construct array two
        count_two_valid_numbers = 0
        count_overlap_numbers = 0

        for current_number in range(1, maximum_value + 1):
            is_divisible_by_divisor_one = (
                current_number % divisor_one == 0
            )
            is_divisible_by_divisor_two = (
                current_number % divisor_two == 0
            )

            if not is_divisible_by_divisor_one:
                count_one_valid_numbers += 1

            if not is_divisible_by_divisor_two:
                count_two_valid_numbers += 1

            if (
                not is_divisible_by_divisor_one
                and not is_divisible_by_divisor_two
            ):
                # Counting shared numbers to check overlap
                count_overlap_numbers += 1

        # Check if conditions are met for the arrays
        if (
            count_one_valid_numbers >= array_one_count
            and count_two_valid_numbers >= array_two_count
            and count_overlap_numbers
            >= array_one_count + array_two_count
            - (maximum_value - (maximum_value // divisor_one)
            - (maximum_value // divisor_two)
            + (maximum_value // ((divisor_one * divisor_two)
            // gcd(divisor_one, divisor_two))))
        ):
            # If all conditions met, return max value
            return maximum_value

        maximum_value += 1

def gcd(number_one, number_two):
    while number_two:
        number_one, number_two = number_two, number_one % number_two
    return number_one

Big(O) Analysis

Time Complexity

O(n*log(n)) – The brute force approach iterates through potential maximum values from 1 up to some upper bound 'n', where 'n' represents the final answer. For each maximum value, we check if we can construct the two arrays. This check involves counting numbers not divisible by divisor1 and divisor2 up to the current maximum value, which takes O(1) time. Therefore, for each maximum value, the divisibility checks are constant. However, since we may need to search up to a value 'n' that could be large, and we are checking each potential maximum to find the *minimum* maximum that works, we can apply binary search to improve the time complexity. The binary search would have log(n) steps, and within each of these steps we do constant work for constructing and comparing. As a result, the overall time complexity becomes O(log(n) * check), where check is O(n) at worst, yielding O(n*log(n)) if we search from 1 to n one by one. Note that binary search improves on a linear approach, changing it from O(n^2) to O(n log n).

Space Complexity

O(1) – The brute force solution, as described, does not use any auxiliary data structures. It only increments a potential maximum value and performs divisibility checks, storing a few boolean values temporarily during the checks. The space required for these variables remains constant irrespective of the potential maximum value which depends on the problem constraints not explicitly defined as input size N. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The most efficient way to solve this involves finding the smallest possible maximum value that satisfies specific conditions about divisibility. Instead of checking every single number, we cleverly narrow down the possibilities to find the ideal answer quickly using a binary search approach.

Here's how the algorithm would work step-by-step:

Realize that the answer we're looking for must fall within a certain range, from the smallest possible number up to a reasonable upper limit.
Pick a number in the middle of that range and imagine that it is the maximum value we're testing.
Figure out how many numbers smaller than our chosen maximum are divisible by the first special number, and how many are divisible by the second special number.
Also, figure out how many numbers smaller than our chosen maximum are divisible by BOTH special numbers.
Combine these counts to see if it is possible to fill the two lists with the required number of unique elements, given our chosen maximum value.
If it is possible, this means our chosen maximum is high enough, so we can try a smaller maximum value in the next step.
If it is not possible, this means our chosen maximum is too low, and we need to try a larger maximum value.
Keep repeating the process of guessing a middle value, checking if it works, and adjusting our guess up or down, until we find the smallest maximum value that satisfies all the divisibility conditions.

Code Implementation

def minimize_maximum(divisor1, divisor2, unique_count1, unique_count2):
    low = 1
    high = 2 * 10**9

    while low < high:
        mid = (low + high) // 2

        # Number of integers divisible by divisor1
        divisible_by_divisor1 = mid // divisor1
        # Number of integers divisible by divisor2
        divisible_by_divisor2 = mid // divisor2
        # Number of integers divisible by both
        divisible_by_both = mid // (divisor1 * divisor2 // gcd(divisor1, divisor2))

        # unique to arr1 and arr2 are calculated
        unique_to_array1 = mid - divisible_by_divisor1
        unique_to_array2 = mid - divisible_by_divisor2

        # Check if the current mid is a possible solution
        if unique_to_array1 >= unique_count1 and unique_to_array2 >= unique_count2 and \
           unique_to_array1 + unique_to_array2 - (mid - divisible_by_divisor1 - mid + divisible_by_divisor2 + divisible_by_both) >= unique_count1 + unique_count2 - (mid - divisible_by_divisor1 - mid + divisible_by_divisor2 + divisible_by_both):
            high = mid
        else:
            low = mid + 1

    return low

def gcd(first_number, second_number):
    # Calculates the greatest common divisor
    while second_number:
        first_number, second_number = second_number, first_number % second_number
    return first_number

Big(O) Analysis

Time Complexity

O(log(n)) – The algorithm performs a binary search within a range of potential maximum values, where 'n' represents the upper bound of that range, which is related to the sizes of the input arrays (n1, n2) and the special divisors. Each step of the binary search involves a constant amount of arithmetic operations to check the feasibility of the current maximum value, primarily involving division and comparison. Since binary search halves the search space at each step, the number of steps is logarithmic with respect to the initial range (n). Therefore, the overall time complexity is O(log(n)).

Space Complexity

O(1) – The algorithm primarily utilizes binary search to find the minimum maximum value. This involves storing a few variables like the lower bound, upper bound, and middle value during the search. Since the number of variables used remains constant regardless of the input array sizes (n1, n2) and the divisibility numbers (divisor1, divisor2), the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
divisor1 or divisor2 is 1	The LCM calculation should handle this correctly, with lcm(1, x) = x, impacting search range but not correctness.
divisor1 and divisor2 are equal	The LCM calculation needs to avoid division by zero, and the inclusion/exclusion principle must consider this equality.
nums1 or nums2 is negative, or a negative n value is passed.	The problem constraints state that these values should be positive, and can be assumed; error handling should address invalid inputs.
n is very large, approaching integer limits.	Integer overflow in calculations like multiplication and LCM should be checked, promoting to larger data types if necessary.
lcm(divisor1, divisor2) close to integer limit	Integer overflow could occur, so perform multiplication carefully, and potentially use a larger integer type.
no value of 'val' satisfies the condition where we have enough distinct numbers in each array	The binary search should converge correctly and the return value should be the smallest possible 'val' that meets the specified conditions.
divisor1 divides divisor2, or vice-versa	The LCM calculation should correctly compute the larger divisor, and the inclusion/exclusion calculation should handle the simplified counting.
n is zero	This edge case would violate the problem's implicit constraint of requiring n to be positive to satisfy the conditions; handle as invalid input.

divisor1 or divisor2 is 1

How to Handle:

The LCM calculation should handle this correctly, with lcm(1, x) = x, impacting search range but not correctness.

divisor1 and divisor2 are equal

How to Handle:

The LCM calculation needs to avoid division by zero, and the inclusion/exclusion principle must consider this equality.

nums1 or nums2 is negative, or a negative n value is passed.

How to Handle:

The problem constraints state that these values should be positive, and can be assumed; error handling should address invalid inputs.

n is very large, approaching integer limits.

How to Handle:

Integer overflow in calculations like multiplication and LCM should be checked, promoting to larger data types if necessary.

lcm(divisor1, divisor2) close to integer limit

How to Handle:

Integer overflow could occur, so perform multiplication carefully, and potentially use a larger integer type.

no value of 'val' satisfies the condition where we have enough distinct numbers in each array

How to Handle:

The binary search should converge correctly and the return value should be the smallest possible 'val' that meets the specified conditions.

divisor1 divides divisor2, or vice-versa

How to Handle:

The LCM calculation should correctly compute the larger divisor, and the inclusion/exclusion calculation should handle the simplified counting.

n is zero

How to Handle:

This edge case would violate the problem's implicit constraint of requiring n to be positive to satisfy the conditions; handle as invalid input.