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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimize the Maximum of Two Arrays

Number: 2628

Difficulty: Medium

Paid? No

Companies: Goldman Sachs

Problem Description

We are given two initially empty arrays arr1 and arr2. We need to add positive integers to these arrays such that: • arr1 contains uniqueCnt1 distinct positive integers, none of which is divisible by divisor1. • arr2 contains uniqueCnt2 distinct positive integers, none of which is divisible by divisor2. • No integer appears in both arrays. The goal is to minimize the maximum integer used in either array.

Key Insights

  • The challenge can be solved using binary search on the candidate maximum value X.
  • For a given X, count numbers in [1, X] that are eligible for arr1 (not divisible by divisor1) and for arr2 (not divisible by divisor2).
  • Some numbers are valid for both arrays (i.e. numbers not divisible by either divisor) and can be shared between arr1 and arr2.
  • It is best to first assign numbers that are exclusively valid for one array, and then use the common pool to satisfy the remaining requirement.
  • Check feasibility by computing: • only1 = numbers valid only for arr1 • only2 = numbers valid only for arr2 • common = numbers valid for both arrays
  • Use binary search to find the smallest X such that the common numbers can cover the residual requirements for both arrays.

Space and Time Complexity

Time Complexity: O(log N) where N is the search space for the maximum number (based on the answer). Space Complexity: O(1)

Solution

We use binary search on the candidate maximum integer X. For a given X, calculate:

  1. common = X - (floor(X/divisor1) + floor(X/divisor2) - floor(X/lcm))
  2. only1 = (X - floor(X/divisor1)) - common (numbers that are valid only for arr1)
  3. only2 = (X - floor(X/divisor2)) - common (numbers that are valid only for arr2)

Then, the additional numbers needed: • req1 = max(0, uniqueCnt1 - only1) • req2 = max(0, uniqueCnt2 - only2)

If req1 + req2 ≤ common then X is a feasible candidate. The binary search finds the minimum X which meets these conditions.

Code Solutions

def lcm(a, b):
    # Helper function to compute LCM using the GCD
    from math import gcd
    return a * b // gcd(a, b)

def minimizeMax(divisor1, divisor2, uniqueCnt1, uniqueCnt2):
    low, high = 1, 10**18  # choose a sufficiently high upper bound
    common_divisor = lcm(divisor1, divisor2)
    
    while low < high:
        mid = (low + high) // 2
        # Count numbers in [1, mid] that are divisible by divisor1, divisor2, and both (via LCM)
        cnt_div1 = mid // divisor1
        cnt_div2 = mid // divisor2
        cnt_common = mid // common_divisor
        
        # Numbers valid for arr1 are those not divisible by divisor1
        total_valid1 = mid - cnt_div1
        # Numbers valid for arr2 are those not divisible by divisor2
        total_valid2 = mid - cnt_div2
        
        # Count numbers valid for both arrays: not divisible by divisor1 and not divisible by divisor2
        common = mid - (cnt_div1 + cnt_div2 - cnt_common)
        # Numbers exclusive to arr1 and arr2 can be derived by subtracting common from total valid ones
        only1 = total_valid1 - common
        only2 = total_valid2 - common
        
        # Compute the extra numbers required from the common pool
        req1 = max(0, uniqueCnt1 - only1)
        req2 = max(0, uniqueCnt2 - only2)
        
        if req1 + req2 <= common:
            high = mid
        else:
            low = mid + 1
    return low

# Example usage:
print(minimizeMax(2, 7, 1, 3))  # Expected output: 4
print(minimizeMax(3, 5, 2, 1))  # Expected output: 3
print(minimizeMax(2, 4, 8, 2))  # Expected output: 15
← Back to All Questions