Minimize the Maximum of Two Arrays Solution in Java

Problem Description

So, you want to minimize the maximum of two arrays? Imagine you have two groups of friends, and you want to invite a certain number of unique friends from each group without inviting anyone who is a total bore (i.e., divisible by certain numbers). The challenge is to figure out the smallest number you can invite while still meeting your unique friend count requirements.

In more technical terms, given two divisors and the number of unique integers you want from each divisor, the goal is to find the smallest integer m such that you can select the required unique integers from the range [1..m].

Code Solution


class Solution {
  public int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
    final long divisorLcm = lcm(divisor1, divisor2);
    long l = 0;
    long r = Integer.MAX_VALUE;

    while (l < r) {
      final long m = (l + r) / 2;
      if (isPossible(m, divisorLcm, divisor1, divisor2, uniqueCnt1, uniqueCnt2))
        r = m;
      else
        l = m + 1;
    }

    return (int) l;
  }

  private boolean isPossible(long m, long divisorLcm, int divisor1, int divisor2, int uniqueCnt1,
                             int uniqueCnt2) {
    final long cnt1 = m - m / divisor1;
    final long cnt2 = m - m / divisor2;
    final long totalCnt = m - m / divisorLcm;
    return cnt1 >= uniqueCnt1 && cnt2 >= uniqueCnt2 && totalCnt >= uniqueCnt1 + uniqueCnt2;
  }

  private long gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
  }

  private long lcm(int a, int b) {
    return a * (b / gcd(a, b));
  }
}

Approach

The solution employs a binary search strategy to efficiently find the minimum value of m. The key steps are:

Calculate the least common multiple (LCM) of the two divisors.
Use binary search to find the smallest m such that the number of integers not divisible by either divisor meets the unique count requirements.
The helper function isPossible checks if a given m can satisfy the unique count conditions.

Time and Space Complexity

Time Complexity: O(log(maxValue)), where maxValue is the maximum integer value we are searching through. The binary search reduces the search space logarithmically.

Space Complexity: O(1), as we are using a constant amount of space for variables.

Real-World Example

Imagine you’re organizing a party and you want to invite friends from two different circles. You want to ensure that you invite a specific number of unique friends from each circle, but you also want to avoid inviting anyone who is a total bore (let’s say, anyone whose name is divisible by 3 or 5). The problem is to find the smallest number of friends you can invite while still meeting your unique count requirements.