Skip to main content

Binary Search

Minimize the Maximum of Two Arrays Solution in C++/Java/Python/JS

minimize-the-maximum-of-two-arrays-problem-description
minimize-the-maximum-of-two-arrays-problem-description

Minimize the Maximum of Two Arrays 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.

Examples:

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.

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.

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⁹

Brute Force Approach

We have two empty arrays:

  • arr1 should contain uniqueCnt1 distinct numbers that are not divisible by divisor1.
  • arr2 should contain uniqueCnt2 distinct numbers that are not divisible by divisor2.
  • No number should be present in both arrays.

And our task? Find the minimum possible maximum integer that can be present in either array.

An initial thought might be:

“Let’s just keep adding numbers one by one and filling the arrays.”

This sounds logical, right? Start from 1, check if the number is valid for either array and keep going until we get the required counts. But there's a big problem:

How do we handle numbers that could belong to both arrays?

When we simulate this approach by checking numbers one by one, we run into ambiguity. Some numbers are not divisible by divisor1 (so they can go into arr1) but also not divisible by divisor2 (so they can go into arr2). How do we decide where to place them? If we assign a number to arr1, does that block it from being in arr2 later?

This confusion forces us to rethink how we are adding numbers. Instead of checking one by one blindly, let’s take a more structured approach.

Let’s say we have divisor1 = 3, divisor2 = 4, uniqueCnt1 = 2, uniqueCnt2 = 2.

We start checking numbers one by one:

  • 1 is not divisible by 3 or 4, so it can go into either arr1 or arr2.
  • 2 is also not divisible by 3 or 4, so it can also go into either arr1 or arr2.
  • 3 is divisible by 3 but not by 4, meaning it can only go into arr2.
  • 4 is divisible by 4 but not by 3, meaning it can only go into arr1.
  • 5 is not divisible by either 3 or 4, so it too can go into either arr1 or arr2.

Now the issue arises: should we put 1 and 2 in arr1 first, or should we save them for arr2? What if we make a choice now that leaves arr2 with a greater maximum number later? This uncertainty forces us to rethink our approach. Instead of checking numbers one by one blindly, we need a more structured way to count and distribute numbers efficiently.

Since we want to minimize the maximum number, the best strategy is to always pick the smallest valid numbers first. This means we start at 1 and gradually increase our candidate numbers.

However, instead of checking each number individually like before, let’s analyze the mathematical properties of the numbers we’re adding.

Now, let's say we pick a number X and check how many numbers we can use below or equal to X. To do this, we need to break down the numbers into different categories.

Category 1: Numbers NOT Divisible by divisor1

We need uniqueCnt1 numbers in arr1, which means we must count how many numbers ≤ X are not divisible by divisor1.

A number N is divisible by divisor1 if N % divisor1 == 0. This means that all numbers that are multiples of divisor1 need to be excluded.

How many numbers ≤ X are divisible by divisor1?
X / divisor1 (integer division)

How many numbers ≤ X are NOT divisible by divisor1?
X - (X / divisor1)

This gives us the count of numbers that are allowed in arr1.

Example: Let’s take X = 10 and divisor1 = 3

  • Numbers ≤ 10: {1,2,3,4,5,6,7,8,9,10}
  • Multiples of 3: {3,6,9} (these are invalid)
  • Non-multiples: {1,2,4,5,7,8,10} (valid for arr1)
  • Count: 10 - (10 / 3) = 10 - 3 = 7

Now we know how to calculate valid numbers for arr1.

Category 2: Numbers NOT Divisible by divisor2

For arr2, we need uniqueCnt2 numbers that are NOT divisible by divisor2. We follow the same process:

  • Numbers ≤ X that are divisible by divisor2 = X / divisor2
  • Numbers ≤ X that are NOT divisible by divisor2 = X - (X / divisor2)

Example: Let’s take X = 10 and divisor2 = 4

  • Multiples of 4: {4,8}
  • Non-multiples: {1,2,3,5,6,7,9,10}
  • Count: 10 - (10 / 4) = 10 - 2 = 8

Category 3: Numbers That Are NOT Divisible by Both divisor1 and divisor2 (Exclusive Numbers)

Some numbers will be valid for both arr1 and arr2, and we need to ensure that we don’t double count them.

Numbers that are multiples of both divisor1 and divisor2 are multiples of their Least Common Multiple (LCM).

So, how many numbers ≤ X are divisible by both divisor1 and divisor2?
X / LCM(divisor1, divisor2)

And how many numbers are not divisible by either divisor1 or divisor2?
X - (X / divisor1) - (X / divisor2) + (X / LCM(divisor1, divisor2))

Why do we add (X / LCM(divisor1, divisor2)) back?
Because we subtracted those numbers twice, once in X / divisor1 and once in X / divisor2, so we must add them back.

Example: Let’s take X = 12, divisor1 = 3, divisor2 = 4

  • Multiples of 3: {3,6,9,12} (count = 4)
  • Multiples of 4: {4,8,12} (count = 3)
  • Multiples of LCM(3,4) = 12: {12} (count = 1)

Total unique numbers not divisible by either divisor1 or divisor2:
12 - (12 / 3) - (12 / 4) + (12 / 12)
12 - 4 - 3 + 1 = 6

This ensures we are counting only valid numbers that are not in conflict.

When we compute exclusive1 (numbers that are only valid for arr1) and exclusive2 (numbers that are only valid for arr2), sometimes these numbers are not enough to fulfill uniqueCnt1 and uniqueCnt2.

Understanding the Deficit Calculation

Now, let's calculate what happens when the numbers available for arr1 or arr2 are not enough to meet their required counts.

We calculate how many numbers we are missing in each array:

  1. Deficit in arr1 (deficit1)
    • If exclusive1 (numbers only valid for arr1) is less than uniqueCnt1, we must borrow numbers from the common pool.
    • If the count of exclusive1 is less than uniqueCnt1, we need more numbers from the common pool.
    • So, we calculate the deficit as:
      deficit1 = uniqueCnt1 - exclusive1 (if exclusive1 is not enough, otherwise 0).
  2. Deficit in arr2 (deficit2)
    • If the count of exclusive2 is less than uniqueCnt2, we also need more numbers from the common pool.
    • So, we calculate the deficit as:
      deficit2 = uniqueCnt2 - exclusive2 (if exclusive2 is not enough, otherwise 0).

How Do We Handle This Deficit?

Once we know the deficits for both arr1 and arr2, we must see if the common pool can fill those gaps.

Step 1: Calculate the Total Deficit

The total deficit is the sum of both deficits:
totalDeficit = deficit1 + deficit2

Step 2: Check If the Common Pool Can Cover the Deficit

If the total deficit is less than or equal to the size of the common pool:
The common pool can fill the gap.

If the total deficit is greater than the size of the common pool:
The common pool is not enough, and we must increase X to gather more valid numbers.

Example for Common Pool Deficit Handling, Suppose:

  • deficit1 = 2
  • deficit2 = 3
  • common = 6

The total deficit is:
totalDeficit = 2 + 3 = 5

Since totalDeficit (5) is less than common (6), the common pool is sufficient.

But if the common pool was 4, we’d need to increase X to gather more numbers.

💡
Try it Yourself!

Let's understand with an example:

Minimize the Maximum of Two Arrays Example:

Input:

  • divisor1 = 2, divisor2 = 4
  • uniqueCnt1 = 8, uniqueCnt2 = 2

Goal:

We need to find the smallest number X such that:

  1. There are at least 8 numbers (for arr1) that are NOT divisible by 2.
  2. There are at least 2 numbers (for arr2) that are NOT divisible by 4.

Step 1: Understand the Conditions

We'll break the numbers into three categories:

  1. Numbers NOT divisible by divisor1 (2):
    • Formula: X - (X / 2)
    • This count must be ≥ 8 for arr1.
  3. Numbers NOT divisible by divisor2 (4):
    • Formula: X - (X / 4)
    • This count must be ≥ 2 for arr2.
  5. Numbers NOT divisible by BOTH divisor1 and divisor2 (Exclusive Numbers):
    • Since the LCM of 2 and 4 is 4, the formula becomes:
      X - (X / 2) - (X / 4) + (X / LCM(2, 4))
    • These are numbers that can be freely used for arr1 or arr2.

Step 2: Start Checking Values from X = 1

We'll start with X = 1 and gradually increase it until we meet all conditions.

Step 3: Brute Force Calculation

We'll check each value step by step, but to save time, we'll skip some values where it's clear they won't meet the required conditions. For example, if X = 10 is too small, we can jump ahead to larger values rather than checking each number one by one.

  • X = 1:
    • Numbers ≤ 1 not divisible by 2 = 1 - (1 / 2) = 1 → (Too few for arr1)
    • Numbers ≤ 1 not divisible by 4 = 1 - (1 / 4) = 1 → (Too few for arr2)
      Not enough numbers.
  • X = 10:
    • Numbers ≤ 10 not divisible by 2 = 10 - (10 / 2) = 10 - 5 = 5 → (Still too few for arr1)
    • Numbers ≤ 10 not divisible by 4 = 10 - (10 / 4) = 10 - 2 = 8 → (Enough for arr2)
      Not enough numbers for arr1.
  • X = 15:
    • Numbers ≤ 15 not divisible by 2 = 15 - (15 / 2) = 15 - 7 = 8 → (Exactly enough for arr1 )
    • Numbers ≤ 15 not divisible by 4 = 15 - (15 / 4) = 15 - 3 = 12 → (More than enough for arr2 )
      All conditions are satisfied.

Step 4: Verify Exclusive and Deficit Numbers

  • Exclusive Numbers (not divisible by 2 or 4):
    X - (X / 2) - (X / 4) + (X / 4)
    = 15 - 7 - 3 + 3 = 8
  • Exclusive numbers are sufficient, so no additional numbers are needed to meet the required count.

Step 5: Final Answer

The smallest value of X that meets all conditions is 15.

Steps to Implement the Solution:

  1. Initialize X to 1
    • Start iterating from X = 1, increasing it step by step until all conditions are met.
  3. Calculate Counts for Divisibility
    • Find how many numbers ≤ X are divisible by divisor1 and divisor2 using:
      • countDiv1 = X / divisor1
      • countDiv2 = X / divisor2
    • Compute LCM(divisor1, divisor2) to determine numbers divisible by both.
      • countDivBoth = X / LCM(divisor1, divisor2)
  5. Determine Allowed and Common Numbers
    • allowed1 → Numbers not divisible by divisor1 → X - countDiv1
    • allowed2 → Numbers not divisible by divisor2 → X - countDiv2
    • common → Numbers not divisible by either divisor
      • common = X - (countDiv1 + countDiv2 - countDivBoth)
  7. Find Exclusively Available Numbers
    • exclusive1 = allowed1 - common (Valid only for arr1)
    • exclusive2 = allowed2 - common (Valid only for arr2)
  9. Calculate Deficits
    • deficit1 → How many extra numbers arr1 needs beyond exclusives
      • deficit1 = max(0, uniqueCnt1 - exclusive1)
    • deficit2 → How many extra numbers arr2 needs beyond exclusives
      • deficit2 = max(0, uniqueCnt2 - exclusive2)
  11. Check If X Is the Answer
    • If (deficit1 + deficit2) ≤ common, return X (as it satisfies all constraints).
    • Otherwise, increment X and continue.

Minimize the Maximum of Two Arrays Leetcode Solution

Minimize the Maximum of Two Arrays / Code Implementation
1. Minimize the Maximum of Two Arrays solution in c++ Try on Compiler 
class Solution {
public:
    int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
        
        // Start from X = 1 and increase until conditions are satisfied
        long long X = 1;

        while (true) {
            
            // Count numbers in [1, X] that are divisible by divisor1
            long long countDiv1 = X / divisor1;

            // Count numbers in [1, X] that are divisible by divisor2
            long long countDiv2 = X / divisor2;

            // Calculate the Least Common Multiple (LCM) of divisor1 and divisor2
            long long lcm = (long long)divisor1 * divisor2 / std::gcd(divisor1, divisor2);

            // Count numbers in [1, X] that are divisible by both divisor1 and divisor2
            long long countDivBoth = X / lcm;
            
            // Calculate numbers that are allowed for arr1 (not divisible by divisor1)
            long long allowed1 = X - countDiv1;

            // Calculate numbers that are allowed for arr2 (not divisible by divisor2)
            long long allowed2 = X - countDiv2;

            // Calculate common numbers that are allowed for both (not divisible by either divisor)
            long long common = X - (countDiv1 + countDiv2 - countDivBoth);
            
            // Calculate exclusive numbers for arr1 (not common)
            long long exclusive1 = allowed1 - common;

            // Calculate exclusive numbers for arr2 (not common)
            long long exclusive2 = allowed2 - common;
            
            // Calculate how many extra numbers arr1 needs beyond exclusives
            long long deficit1 = (uniqueCnt1 > exclusive1) ? (uniqueCnt1 - exclusive1) : 0;

            // Calculate how many extra numbers arr2 needs beyond exclusives
            long long deficit2 = (uniqueCnt2 > exclusive2) ? (uniqueCnt2 - exclusive2) : 0;
            
            // If common numbers can cover both deficits, return the minimum X
            if (deficit1 + deficit2 <= common)
                return X;
            
            // Increment X and check again
            X++;
        }
    }
};

2. Minimize the Maximum of Two Arrays solution in Java Try on Compiler 
class Solution {
    public int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
        
        // Start from X = 1 and increase until conditions are satisfied
        long X = 1;

        while (true) {
            
            // Count numbers in [1, X] that are divisible by divisor1
            long countDiv1 = X / divisor1;

            // Count numbers in [1, X] that are divisible by divisor2
            long countDiv2 = X / divisor2;

            // Calculate the Least Common Multiple (LCM) of divisor1 and divisor2
            long lcm = lcm(divisor1, divisor2);

            // Count numbers in [1, X] that are divisible by both divisor1 and divisor2
            long countDivBoth = X / lcm;
            
            // Calculate numbers that are allowed for arr1 (not divisible by divisor1)
            long allowed1 = X - countDiv1;

            // Calculate numbers that are allowed for arr2 (not divisible by divisor2)
            long allowed2 = X - countDiv2;

            // Calculate common numbers that are allowed for both (not divisible by either divisor)
            long common = X - (countDiv1 + countDiv2 - countDivBoth);
            
            // Calculate exclusive numbers for arr1 (not common)
            long exclusive1 = allowed1 - common;

            // Calculate exclusive numbers for arr2 (not common)
            long exclusive2 = allowed2 - common;
            
            // Calculate how many extra numbers arr1 needs beyond exclusives
            long deficit1 = Math.max(0, uniqueCnt1 - exclusive1);

            // Calculate how many extra numbers arr2 needs beyond exclusives
            long deficit2 = Math.max(0, uniqueCnt2 - exclusive2);
            
            // If common numbers can cover both deficits, return the minimum X
            if (deficit1 + deficit2 <= common)
                return (int) X;
            
            // Increment X and check again
            X++;
        }
    }

    // Function to compute the Least Common Multiple (LCM)
    private long lcm(int a, int b) {
        return (long) a * b / gcd(a, b);
    }

    // Function to compute the Greatest Common Divisor (GCD)
    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

3. Minimize the Maximum of Two Arrays solution in Python Try on Compiler 
import math

class Solution:
    def minimizeSet(self, divisor1, divisor2, uniqueCnt1, uniqueCnt2):

        def gcd(a, b):
            while b:
                a, b = b, a % b
            return a
        
        # Start from X = 1 and increase until conditions are satisfied
        X = 1
        
        while True:
            
            # Count numbers in [1, X] that are divisible by divisor1
            countDiv1 = X // divisor1

            # Count numbers in [1, X] that are divisible by divisor2
            countDiv2 = X // divisor2

            # Calculate the Least Common Multiple (LCM) of divisor1 and divisor2
            lcm = (divisor1 * divisor2) // gcd(divisor1, divisor2)

            # Count numbers in [1, X] that are divisible by both divisor1 and divisor2
            countDivBoth = X // lcm
            
            # Calculate numbers that are allowed for arr1 (not divisible by divisor1)
            allowed1 = X - countDiv1

            # Calculate numbers that are allowed for arr2 (not divisible by divisor2)
            allowed2 = X - countDiv2

            # Calculate common numbers that are allowed for both (not divisible by either divisor)
            common = X - (countDiv1 + countDiv2 - countDivBoth)
            
            # Calculate exclusive numbers for arr1 (not common)
            exclusive1 = allowed1 - common

            # Calculate exclusive numbers for arr2 (not common)
            exclusive2 = allowed2 - common
            
            # Calculate how many extra numbers arr1 needs beyond exclusives
            deficit1 = max(0, uniqueCnt1 - exclusive1)

            # Calculate how many extra numbers arr2 needs beyond exclusives
            deficit2 = max(0, uniqueCnt2 - exclusive2)
            
            # If common numbers can cover both deficits, return the minimum X
            if deficit1 + deficit2 <= common:
                return X
            
            # Increment X and check again
            X += 1

4. Minimize the Maximum of Two Arrays solution in Javascript Try on Compiler 
var minimizeSet = function(divisor1, divisor2, uniqueCnt1, uniqueCnt2) {
    
    // Start from X = 1 and increase until conditions are satisfied
    let X = 1;

    while (true) {
        
        // Count numbers in [1, X] that are divisible by divisor1
        let countDiv1 = Math.floor(X / divisor1);

        // Count numbers in [1, X] that are divisible by divisor2
        let countDiv2 = Math.floor(X / divisor2);

        // Calculate the Least Common Multiple (LCM) of divisor1 and divisor2
        let lcm = (divisor1 * divisor2) / gcd(divisor1, divisor2);

        // Count numbers in [1, X] that are divisible by both divisor1 and divisor2
        let countDivBoth = Math.floor(X / lcm);
        
        // Calculate numbers that are allowed for arr1 (not divisible by divisor1)
        let allowed1 = X - countDiv1;

        // Calculate numbers that are allowed for arr2 (not divisible by divisor2)
        let allowed2 = X - countDiv2;

        // Calculate common numbers that are allowed for both (not divisible by either divisor)
        let common = X - (countDiv1 + countDiv2 - countDivBoth);
        
        // Calculate exclusive numbers
        let exclusive1 = allowed1 - common;
        let exclusive2 = allowed2 - common;
        
        // Calculate deficits
        let deficit1 = Math.max(0, uniqueCnt1 - exclusive1);
        let deficit2 = Math.max(0, uniqueCnt2 - exclusive2);
        
        if (deficit1 + deficit2 <= common) return X;
        
        X++;
    }
};

// Helper function to compute GCD
function gcd(a, b) {
    return b === 0 ? a : gcd(b, a % b);
}

Complexity Analysis of Minimize the Maximum of Two Arrays (brute force):

Time Complexity: O(n)

This approach linearly checks each number from 1 to a large X to find the smallest number that satisfies the given conditions.

  • In the worst case, X might be very large, meaning we need to iterate through almost all numbers up to O(uniqueCnt1 × divisor1 + uniqueCnt2 × divisor2).
  • Since we increment X one by one and check divisibility conditions in O(1) time per iteration, the overall complexity is O(n), where n is the largest number we check.

Space Complexity: O(1)

  1. Auxiliary Space Complexity: O(1)
    The approach only uses a few integer and long long variables (X, countDiv1, countDiv2, allowed1, allowed2, common, etc.).
    Since these variables take O(1) space and no extra data structures (like arrays or hash tables) are used, the auxiliary space complexity remains O(1).
  2. Total Space Complexity: O(1)
    All computations are performed in-place without dynamically allocating memory.
    Thus, the total space complexity of the brute force approach is O(1).

Will Brute Force Work Against the Given Constraints? 

For the current solution, the time complexity is O(n), where n represents the worst-case number we need to iterate through before finding the minimum X that satisfies the given constraints. In this case, n can be as large as 10⁹ (1e9).

In the worst-case scenario, the algorithm iterates from 1 to n, leading to a time complexity of O(n).
This time complexity can become inefficient when n is large, particularly when n is close to its upper bound (1e9). In such cases, the algorithm may perform a large number of operations (nearly 1e9), making it impractical for large inputs.

This solution may not execute efficiently for all test cases, particularly when n is near its upper limit. While it may work for inputs with smaller values of n, it could exceed the time limits for large inputs where n is close to its maximum constraint.

In competitive programming environments, the typical time complexity limit is around 10⁶ operations per test case. Therefore, for inputs with large values of n, this time complexity could lead to inefficient execution.

How to optimize it?

In the previous approach, we checked every possible number starting from 1 and counted how many numbers were not divisible by divisor1 or divisor2 until we reached the required count for arr1 and arr2. This gave us a time complexity of O(n), where n can be as large as 10⁹ (1e9), making it extremely slow and prone to TLE (Time Limit Exceeded).

Now, let’s think about improving this.

The main issue was that we checked every number one by one to see if it could be placed in arr1 or arr2. Since n can be very large, iterating through all numbers takes too much time.

Can we make this part faster?

Yes! Here’s the hint:

We are searching for the minimum possible maximum integer that satisfies all constraints, and we know that it lies somewhere between 1 and 10⁹ (as given in the constraints).

Now that we know the two endpoints, 1 and 10⁹, let's make a few observations:

  1. The data structure is sorted:
    The set of numbers we consider (from 1 to 10⁹) is naturally sorted in increasing order. Since valid numbers are just those not divisible by divisor1 or divisor2, they too appear in sorted order.
  2. The search space is monotonic:
    Imagine you have a function that counts how many numbers not divisible by divisor1 or divisor2 exist up to a number X. Let's call this function countValid(X). The key idea is that as X increases, countValid(X) will either stay the same or increase—it never decreases.

Think of it like climbing stairs:

  • When you’re on a lower step, you’ve selected fewer valid numbers.
  • As you climb higher, you select more valid numbers or at least the same amount if you pause.

Now, if for a certain number X, you have already counted at least (uniqueCnt1 + uniqueCnt2) valid numbers (i.e., countValid(X) ≥ uniqueCnt1 + uniqueCnt2), then moving to any number greater than X won’t invalidate the result—you might even get more valid numbers.
This means every number after X will also have at least uniqueCnt1 + uniqueCnt2 valid numbers up to that point.

Conversely, if at X, you haven’t reached the required count, then any number smaller than X will also have fewer valid numbers.

This one-way behavior is what we call monotonicity. It allows us to use binary search because once we find a value of X that meets or exceeds the required count, we know that all larger values will also work, and if X doesn’t work, then no smaller number will work either.

  1. The middle element helps minimize or maximize the search space:
    Instead of checking every possible number from 1 to 10⁹, we can take the middle value of our current search range and use our countValid(X) function to decide which half of the range to keep:

    If the middle value mid produces a count that is at least (uniqueCnt1 + uniqueCnt2) (i.e., we can construct at least that many valid numbers up to mid), then mid is a valid candidate. We then move to the left half of the range to see if there’s a smaller valid number.

    If the count for mid is less than (uniqueCnt1 + uniqueCnt2), then mid is too small, and we must search in the right half for a number that produces enough valid numbers.

Imagine plotting a graph with the potential values on the x-axis and the corresponding count of valid numbers on the y-axis. As X increases, the count of valid numbers increases monotonically.
Before a certain threshold, the count is below (uniqueCnt1 + uniqueCnt2); after crossing that threshold, the count is at least (uniqueCnt1 + uniqueCnt2).

That threshold is exactly the minimum possible maximum integer that satisfies all conditions.

minimize-the-maximum-of-two-arrays-graph

Thus, by leveraging the sorted and monotonic properties of the range, we can apply binary search to quickly narrow down and pinpoint the smallest X for which the count of valid numbers ≤ X is at least (uniqueCnt1 + uniqueCnt2).

💡
How binary search works?

Binary Search Approach to Minimize the Maximum of Two Arrays

Binary search helps us efficiently determine the minimum possible X that satisfies the given constraints. Instead of checking every value linearly, we narrow the search space at each step.

  1. Define Search Space:
    • The minimum possible X is 1.
    • The maximum possible X is a sufficiently large value (e.g., 10¹⁰).
  2. Perform Binary Search:
    • Compute mid as the average of left and right.
    • Check if mid is a valid maximum using the valid function.
    • If mid satisfies the conditions (i.e., we can form both arrays with required unique elements), store it as a potential answer and move to the left half (right = mid - 1) to find a smaller valid value.
    • Otherwise, move to the right half (left = mid + 1) to find a larger valid value.
  3. Terminate When Search Space Ends:
    • The stored ans holds the minimum X that meets all conditions.
    • This is returned as the final result.

By using binary search, we reduce the problem's complexity from O(n) to O(log n), significantly improving performance and avoiding TLE issues.

Let us understand this with a video.

0:00
/3:11

minimize-the-maximum-of-two-arrays-optimal-approach-animation

💡
Try it Yourself!

Let's understand with an example:

Minimize the Maximum of Two Arrays Example:

Input:

divisor1 = 2, divisor2 = 4, uniqueCnt1 = 8, uniqueCnt2 = 2

Step-by-step Execution:

  1. Binary Search Initialization:
  • Left = 1, Right = 10¹⁰, Answer = 10¹⁰

Binary Search Iterations (Finding Minimum X):

  • Mid = 5 × 10⁹ → valid(5 × 10⁹) == true → Update Answer = 5 × 10⁹, move Right = (5 × 10⁹) - 1
  • Mid = 2.5 × 10⁹ → valid(2.5 × 10⁹) == true → Update Answer = 2.5 × 10⁹, move Right = (2.5 × 10⁹) - 1(Binary search keeps narrowing down)
  • Mid = 15 → valid(15) == true → Update Answer = 15, move Right = 14
  • Mid = 14 → valid(14) == false → Move Left = 15
  • Mid = 15 → valid(15) == true (found minimum valid X)
  1. Key Calculations for X = 15:
  • CountDiv1 (div by 2): ⌊15 / 2⌋ = 7
  • CountDiv2 (div by 4): ⌊15 / 4⌋ = 3
  • CountDivBoth (div by LCM(2,4) = 4): ⌊15 / 4⌋ = 3
  • Allowed for arr1: 15 - 7 = 8
  • Allowed for arr2: 15 - 3 = 12
  • Common Numbers: 15 - (7 + 3 - 3) = 8
  • Exclusive for arr1: 8 - 8 = 0
  • Exclusive for arr2: 12 - 8 = 4
  • Deficit for arr1: max(8 - 0, 0) = 8
  • Deficit for arr2: max(2 - 4, 0) = 0
  • Common covers deficits: 8 + 0 ≤ 8 → Valid X = 15

Final Answer: Minimum possible maximum integer = 15

How to code it up:

  1. Set up Binary Search:
    • Initialize left = 1 and right = 1e10 to search for the smallest valid maximum X.
  3. Implement the Binary Search:
    • Compute mid = (left + right) / 2.
    • If mid satisfies the conditions, update ans = mid and search for a smaller X (right = mid - 1).
    • Otherwise, increase the search space (left = mid + 1).
  5. Define a Helper Function (valid(X)) to Check Feasibility:
    • Count numbers divisible by divisor1, divisor2, and their LCM.
    • Determine numbers allowed for arr1, arr2, and common numbers (not divisible by either).
    • Calculate exclusive numbers for each array and any deficit if exclusives are insufficient.
    • If the common numbers can cover both deficits, X is valid.
  7. Return the Minimum Valid X Found.

Minimize the Maximum of Two Arrays Leetcode Solution

Minimize the Maximum of Two Arrays / Code Implementation
1. Minimize the Maximum of Two Arrays solution in c++ Try on Compiler 
class Solution {
public:

    // Helper function that checks if X is a valid maximum
    // by verifying if we can satisfy both arrays' requirements.
    bool valid(long long X, int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
        // Count numbers in [1, X] divisible by divisor1
        long long countDiv1 = X / divisor1;
        
        // Count numbers in [1, X] divisible by divisor2
        long long countDiv2 = X / divisor2;
        
        // Calculate Least Common Multiple (LCM) of divisor1 and divisor2
        long long lcm = (long long)divisor1 * divisor2 / __gcd(divisor1, divisor2);
        
        // Count numbers in [1, X] divisible by both divisor1 and divisor2
        long long countDivBoth = X / lcm;
        
        // Allowed for arr1: numbers not divisible by divisor1
        long long allowed1 = X - countDiv1;
        
        // Allowed for arr2: numbers not divisible by divisor2
        long long allowed2 = X - countDiv2;
        
        // Common: numbers allowed for both (not divisible by either divisor)
        long long common = X - (countDiv1 + countDiv2 - countDivBoth);
        
        // Exclusively available for arr1 (only valid for arr1, not common)
        long long exclusive1 = allowed1 - common;
        
        // Exclusively available for arr2 (only valid for arr2, not common)
        long long exclusive2 = allowed2 - common;
        
        // Calculate deficit for arr1 if exclusive numbers are not enough
        long long deficit1 = (uniqueCnt1 > exclusive1) ? (uniqueCnt1 - exclusive1) : 0;
        
        // Calculate deficit for arr2 if exclusive numbers are not enough
        long long deficit2 = (uniqueCnt2 > exclusive2) ? (uniqueCnt2 - exclusive2) : 0;
        
        // X is valid if the available common numbers can cover both deficits
        return (deficit1 + deficit2 <= common);
    }
    
    int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {

        // Define search space boundaries.
        // We set right to a sufficiently large number.
        long long left = 1, right = 1e10, ans = right;
        
        // Binary search to find the minimum X satisfying the condition.
        while (left <= right) {
            long long mid = left + (right - left) / 2;
            
            // Check if mid is a valid maximum
            if (valid(mid, divisor1, divisor2, uniqueCnt1, uniqueCnt2)) {
                ans = mid;

                // Try to find a smaller valid maximum
                right = mid - 1; 
            } else {
                left = mid + 1;
            }
        }
        return (int)ans;
    }
};

2. Minimize the Maximum of Two Arrays solution in Java Try on Compiler 
class Solution {
    
    // Helper function to check if X is a valid maximum value
    private boolean valid(long X, int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
        
        // Count numbers in range [1, X] that are divisible by divisor1
        long countDiv1 = X / divisor1;
        
        // Count numbers in range [1, X] that are divisible by divisor2
        long countDiv2 = X / divisor2;
        
        // Compute Least Common Multiple (LCM) of divisor1 and divisor2
        long lcm = (long) divisor1 * divisor2 / gcd(divisor1, divisor2);
        
        // Count numbers in range [1, X] that are divisible by both divisor1 and divisor2
        long countDivBoth = X / lcm;
        
        // Count of numbers in range [1, X] that are **not** divisible by divisor1
        long allowed1 = X - countDiv1;
        
        // Count of numbers in range [1, X] that are **not** divisible by divisor2
        long allowed2 = X - countDiv2;
        
        // Count of numbers that are **not** divisible by either divisor1 or divisor2
        long common = X - (countDiv1 + countDiv2 - countDivBoth);
        
        // Count of numbers exclusively available for arr1 (not common)
        long exclusive1 = allowed1 - common;
        
        // Count of numbers exclusively available for arr2 (not common)
        long exclusive2 = allowed2 - common;
        
        // Calculate deficit for arr1 if exclusive numbers are not enough
        long deficit1 = Math.max(0, uniqueCnt1 - exclusive1);
        
        // Calculate deficit for arr2 if exclusive numbers are not enough
        long deficit2 = Math.max(0, uniqueCnt2 - exclusive2);
        
        // Check if the available common numbers can cover both deficits
        return (deficit1 + deficit2 <= common);
    }
    
    public int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
        
        // Define search space boundaries
        long left = 1, right = (long) 1e10, ans = right;
        
        // Perform binary search to find the minimum X that satisfies the conditions
        while (left <= right) {
            
            // Compute the mid-point of the search range
            long mid = left + (right - left) / 2;
            
            // Check if mid is a valid maximum
            if (valid(mid, divisor1, divisor2, uniqueCnt1, uniqueCnt2)) {
                
                // If valid, update answer and search for a smaller possible maximum
                ans = mid;
                right = mid - 1;
                
            } else {
                // If not valid, search in the right half
                left = mid + 1;
            }
        }
        
        // Return the minimum possible maximum integer
        return (int) ans;
    }
    
    // Helper function to compute GCD (Greatest Common Divisor)
    private long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

3. Minimize the Maximum of Two Arrays solution in Python Try on Compiler 
class Solution:

    # Function to compute GCD (Greatest Common Divisor) using Euclidean algorithm
    def gcd(self, a, b):
        while b:
            a, b = b, a % b
        return a

    # Helper function to check if X is a valid maximum
    def valid(self, X, divisor1, divisor2, uniqueCnt1, uniqueCnt2):
        
        # Count numbers in [1, X] divisible by divisor1
        countDiv1 = X // divisor1

        # Count numbers in [1, X] divisible by divisor2
        countDiv2 = X // divisor2

        # Compute Least Common Multiple (LCM) using GCD
        lcm = (divisor1 * divisor2) // self.gcd(divisor1, divisor2)

        # Count numbers in [1, X] divisible by both divisor1 and divisor2
        countDivBoth = X // lcm

        # Allowed numbers for arr1 (not divisible by divisor1)
        allowed1 = X - countDiv1

        # Allowed numbers for arr2 (not divisible by divisor2)
        allowed2 = X - countDiv2

        # Numbers allowed in both (not divisible by either divisor)
        common = X - (countDiv1 + countDiv2 - countDivBoth)

        # Exclusively available for arr1 (valid only for arr1, not common)
        exclusive1 = allowed1 - common

        # Exclusively available for arr2 (valid only for arr2, not common)
        exclusive2 = allowed2 - common

        # Calculate deficit for arr1 if exclusive numbers are insufficient
        deficit1 = max(0, uniqueCnt1 - exclusive1)

        # Calculate deficit for arr2 if exclusive numbers are insufficient
        deficit2 = max(0, uniqueCnt2 - exclusive2)

        # X is valid if the available common numbers can cover both deficits
        return (deficit1 + deficit2 <= common)

    def minimizeSet(self, divisor1, divisor2, uniqueCnt1, uniqueCnt2):
        
        # Define search space boundaries
        left, right = 1, int(1e10)
        ans = right

        # Perform binary search to find the minimum valid maximum value
        while left <= right:
            
            # Compute the middle of the search range
            mid = (left + right) // 2

            # Check if mid is a valid maximum
            if self.valid(mid, divisor1, divisor2, uniqueCnt1, uniqueCnt2):
                
                # Store the current valid answer
                ans = mid

                # Try to find a smaller valid maximum
                right = mid - 1
            else:
                # Search in the right half if mid is too small
                left = mid + 1
        
        # Return the smallest valid maximum found
        return ans

4. Minimize the Maximum of Two Arrays solution in Javascript Try on Compiler 
// Helper function to compute GCD (Greatest Common Divisor)
function gcd(a, b) {
    while (b) {
        let temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Helper function to check if X is a valid maximum value
function valid(X, divisor1, divisor2, uniqueCnt1, uniqueCnt2) {

    // Count numbers in [1, X] divisible by divisor1
    let countDiv1 = Math.floor(X / divisor1);

    // Count numbers in [1, X] divisible by divisor2
    let countDiv2 = Math.floor(X / divisor2);

    // Compute Least Common Multiple (LCM) using GCD
    let lcm = (divisor1 * divisor2) / gcd(divisor1, divisor2);

    // Count numbers in [1, X] divisible by both divisor1 and divisor2
    let countDivBoth = Math.floor(X / lcm);

    // Allowed numbers for arr1 (not divisible by divisor1)
    let allowed1 = X - countDiv1;

    // Allowed numbers for arr2 (not divisible by divisor2)
    let allowed2 = X - countDiv2;

    // Numbers allowed in both (not divisible by either divisor)
    let common = X - (countDiv1 + countDiv2 - countDivBoth);

    // Exclusively available for arr1 (valid only for arr1, not common)
    let exclusive1 = allowed1 - common;

    // Exclusively available for arr2 (valid only for arr2, not common)
    let exclusive2 = allowed2 - common;

    // Calculate deficit for arr1 if exclusive numbers are insufficient
    let deficit1 = Math.max(0, uniqueCnt1 - exclusive1);

    // Calculate deficit for arr2 if exclusive numbers are insufficient
    let deficit2 = Math.max(0, uniqueCnt2 - exclusive2);

    // X is valid if the available common numbers can cover both deficits
    return (deficit1 + deficit2 <= common);
}

// Function to find the minimum valid maximum value
function minimizeSet(divisor1, divisor2, uniqueCnt1, uniqueCnt2) {

    // Define search space boundaries
    let left = 1, right = 1e10, ans = right;

    // Perform binary search to find the minimum valid maximum value
    while (left <= right) {

        // Compute the middle of the search range
        let mid = Math.floor((left + right) / 2);

        // Check if mid is a valid maximum
        if (valid(mid, divisor1, divisor2, uniqueCnt1, uniqueCnt2)) {

            // Store the current valid answer
            ans = mid;

            // Try to find a smaller valid maximum
            right = mid - 1;
        } else {
            // Search in the right half if mid is too small
            left = mid + 1;
        }
    }

    // Return the smallest valid maximum found
    return ans;
}

Time Complexity : O(log n)

The main function minimizeSet() uses binary search over the range [1, 10¹⁰], and in each iteration, it calls the valid() function, which runs in O(1) time.

1. Binary Search Complexity

  • The search space is [1, 10¹⁰], so the number of iterations in binary search is O(log(10¹⁰)).
  • Since log(10¹⁰) ≈ 33, the number of iterations is around 33.

2. valid() Function Complexity

  • The valid() function involves a few constant-time operations:
    • Computing countDiv1, countDiv2, countDivBoth → O(1)
    • Computing LCM using GCD (Euclidean algorithm) → O(log(min(divisor₁, divisor₂)))
    • Performing basic arithmetic calculations → O(1)
  • Since the GCD computation takes at most O(log(min(divisor₁, divisor₂))), the valid() function runs in approximately O(log D), where D = min(divisor₁, divisor₂).
  • However, since D is much smaller than 10¹⁰, we can consider it constant in most cases.

Final Time Complexity

  • Binary search: O(log 10¹⁰) ≈ O(33)
  • Each iteration calls valid() (O(1))
  • Total complexity: O(log 10¹⁰) = O(33) ≈ O(log N)

Final Answer

⏳ Time Complexity: O(log n), where n = 10¹⁰ (upper bound of search space).

Space Complexity : O(1)

  1. Auxiliary Space Complexity: O(1)
    The algorithm only uses a few integer and long long variables for:
    Binary search: (left, right, mid, ans)
    Calculations: (countDiv1, countDiv2, countDivBoth, lcm, gcd, common, exclusive values, deficits)
    Since no additional data structures (arrays, hash tables, etc.) are used, the auxiliary space complexity is O(1).
  2. Total Space Complexity: O(1)
    The input constraints ensure that we only use a constant number of variables.
    Thus, the total space complexity remains O(1).

Similar Problems

Many real-world problems rely on Math to develop efficient solutions. For instance, Binary Search is widely used in algorithms that require optimizing search space, such as finding square roots or solving numerical equations efficiently. In cryptography and encryption, Number Theory plays a fundamental role, particularly in prime factorization and modular arithmetic. By leveraging Math, Binary Search, and Number Theory, we can tackle complex computational challenges, from optimizing algorithms to securing digital communications.

Now that we have successfully tackled this problem, let's try similar problems.

1. Maximum and minimum of an array 

Given an array of size N. The task is to find the maximum and the minimum element of the array using the minimum number of comparisons.

2. Maximum Index

Given an array, arr[] of non-negative integers. The task is to return the maximum of j - i (i<=j) subjected to the constraint of arr[i] <= arr[j].

💡
Showcase your skills by joining LearnYard Technologies FZ-LLC as a Technical Content Writer. Apply now and inspire the next generation of learners—fill out the form: https://forms.gle/CGDsbGkcapSfvXKM8