We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimize the Maximum of Two Arrays

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem requires finding distinct integers that are not divisible by given divisors.
  • The arrays must not share any integers, which adds a constraint to the selection process.
  • The solution can leverage binary search to efficiently find the minimum maximum integer that satisfies the conditions.

Space and Time Complexity

Time Complexity: O(log(max_val)), where max_val is the upper bound for the maximum integer we are searching for.
Space Complexity: O(1), as we use a constant amount of space for variables.

Solution

To solve this problem, we can utilize a binary search approach. The idea is to search for the smallest maximum integer x such that it is possible to fill arr1 and arr2 with the required distinct integers under the given constraints.

  1. Set the search range for x from 1 to a value that guarantees we can find enough integers (for instance, uniqueCnt1 + uniqueCnt2 + max(divisor1, divisor2)).
  2. For each midpoint x, calculate how many integers can be added to arr1 and arr2:
    • Count integers from 1 to x that are not divisible by divisor1 for arr1.
    • Count integers from 1 to x that are not divisible by divisor2 for arr2.
    • Adjust for any overlap between the two counts.
  3. If the counts meet the required unique counts, adjust the binary search range to look for a smaller maximum. Otherwise, increase the maximum.

This algorithm efficiently narrows down to the minimum possible maximum integer.

Code Solutions

def count_not_divisible(n, divisor):
    return n - n // divisor

def can_form_arrays(max_val, uniqueCnt1, uniqueCnt2, divisor1, divisor2):
    count1 = count_not_divisible(max_val, divisor1)
    count2 = count_not_divisible(max_val, divisor2)
    # Adjust for overlap
    count_common = count_not_divisible(max_val, (divisor1 * divisor2) // gcd(divisor1, divisor2))
    
    return (count1 + count2 - count_common) >= (uniqueCnt1 + uniqueCnt2)

def minimizeArrayValue(divisor1, divisor2, uniqueCnt1, uniqueCnt2):
    left, right = 1, uniqueCnt1 + uniqueCnt2 + max(divisor1, divisor2)
    while left < right:
        mid = (left + right) // 2
        if can_form_arrays(mid, uniqueCnt1, uniqueCnt2, divisor1, divisor2):
            right = mid
        else:
            left = mid + 1
    return left
← Back to All Questions