medium Minimize the Maximum of Two Arrays

Problem Statement

Given divisor1, divisor2, uniqueCnt1, and uniqueCnt2 integers, find the smallest possible maximum integer that could be present in either array after they are filled according to the below conditions.

• You can take two arrays arr1 and arr2 which are initially empty.
• arr1 contains total uniqueCnt1 different positive integers, each of them is not divisible by divisor1.
• arr2 contains total uniqueCnt2 different positive integers, each of them is not divisible by divisor2.
• There are no common integers in both arrays.

Examples

Example 1:

• Input: uniqueCnt1 = 2, divisor1 = 2, uniqueCnt2 = 2, divisor2 = 3
• Expected Output: 4
• Explanation: The optimal arrays could be arr1 = [1, 3] (numbers not divisible by 2) and arr2 = [2, 4] (numbers not divisible by 3). The maximum number among both arrays is 4.

Example 2:

• Input: uniqueCnt1 = 3, divisor1 = 3, uniqueCnt2 = 4, divisor2 = 4
• Expected Output: 7
• Explanation: Possible arrays are arr1 = [1, 2, 4] and arr2 = [3, 5, 6, 7]. The highest integer used is 7.

Example 3:

• Input: uniqueCnt1 = 1, divisor1 = 7, uniqueCnt2 = 1, divisor2 = 10
• Expected Output: 2
• Explanation: We can use arr1 = [1] (since it's not divisible by 7) and arr2 = [2] (since it's not divisible by 10). The highest integer here is 2.

Constraints:

• 2 <= divisor1, divisor2 <= 10⁵
• 1 <= uniqueCnt1, uniqueCnt2 < 10⁹
• 2 <= uniqueCnt1 + uniqueCnt2 <= 10⁹

Solution

To solve this problem, the approach involves generating two sets of integers for arr1 and arr2 that adhere to their respective divisibility conditions. This process can be streamlined using a binary search method to determine the smallest possible maximum integer in an efficient manner. By setting an upper and lower bound and validating each midpoint in the binary search, we can check if it's possible to meet the conditions with the current maximum value.

This method is both efficient and effective, as it systematically narrows down the potential maximum value without having to explicitly generate each possible combination of arrays.

Step-by-Step Algorithm

1. Initialize Variables:

   • low is set to the sum of uniqueCnt1 and uniqueCnt2 to ensure there are enough integers available to meet the minimum requirements of both sets.
   • high is set to a divisor1 * divisor2 * uniqueCnt1 * uniqueCnt2, which acts as an initial upper bound for the binary search.

2. Compute Least Common Multiple (LCM):

   • Calculate the least common multiple (LCM) of divisor1 and divisor2 using the gcd function. The LCM is needed to determine how many numbers are divisible by both divisors.

3. Binary Search:

   • Perform a binary search between low and high. In each iteration:
     • Calculate mid, which is the average of low and high.
     • Compute countBoth, the count of numbers up to mid that are divisible by both divisor1 and divisor2.

4. Validity Check:

   • Check if the current mid can accommodate all required conditions:
     • Ensure there are enough numbers after removing those divisible by both divisors (mid - countBoth) to fill both sets.
     • Ensure that after removing numbers divisible by divisor1, there are still at least uniqueCnt1 numbers left.
     • Ensure that after removing numbers divisible by divisor2, there are still at least uniqueCnt2 numbers left.

5. Adjust Search Bounds:

   • If the conditions are satisfied, reduce high to mid - 1 to search for a potentially smaller maximum.
   • If not, increase low to mid + 1 to eliminate too small values.

6. Determine Result:

   • The loop exits when low exceeds high, and low will hold the minimum maximum integer that satisfies all conditions.

Algorithm Walkthrough

Let's consider the Input: uniqueCnt1 = 3, divisor1 = 3, uniqueCnt2 = 4, divisor2 = 4

Initialization:

• low = 7, high = 144, lcm = 12.

Binary Search Process:

• Iteration 1:

  • mid = 75.
  • countBoth = 6.
  • Check conditions:
    • mid - countBoth = 69 (Condition 1: Satisfied).
    • mid - (mid / 3) = 50 (Condition 2: Satisfied).
    • mid - (mid / 4) = 57 (Condition 3: Satisfied).
  • Conditions met, update high = 74.

• Iteration 2:

  • mid = 40.
  • countBoth = 3.
  • Check conditions:
    • mid - countBoth = 37 (Condition 1: Satisfied).
    • mid - (mid / 3) = 27 (Condition 2: Satisfied).
    • mid - (mid / 4) = 30 (Condition 3: Satisfied).
  • Conditions met, update high = 39.

• Iteration 3:

  • mid = 23.
  • countBoth = 1.
  • Check conditions:
    • mid - countBoth = 22 (Condition 1: Satisfied).
    • mid - (mid / 3) = 15 (Condition 2: Satisfied).
    • mid - (mid / 4) = 17 (Condition 3: Satisfied).
  • Conditions met, update high = 22.

• Iteration 4:

  • mid = 14.
  • countBoth = 1.
  • Check conditions:
    • mid - countBoth = 13 (Condition 1: Satisfied).
    • mid - (mid / 3) = 9 (Condition 2: Satisfied).
    • mid - (mid / 4) = 10 (Condition 3: Satisfied).
  • Conditions met, update high = 13.

• Iteration 5:

  • mid = 10.
  • countBoth = 0.
  • Check conditions:
    • mid - countBoth = 10 (Condition 1: Satisfied).
    • mid - (mid / 3) = 7 (Condition 2: Satisfied).
    • mid - (mid / 4) = 8 (Condition 3: Satisfied).
  • Conditions met, update high = 9.

• Iteration 6:

  • mid = 8.
  • countBoth = 0.
  • Check conditions:
    • mid - countBoth = 8 (Condition 1: Satisfied).
    • mid - (mid / 3) = 6 (Condition 2: Satisfied).
    • mid - (mid / 4) = 6 (Condition 3: Just satisfied).
  • Conditions met, update high = 7.

• Iteration 7:

  • mid = 7.
  • countBoth = 0.
  • Check conditions:
    • mid - countBoth = 7 (Condition 1: Just satisfied).
    • mid - (mid / 3) = 5 (Condition 2: Satisfied).
    • mid - (mid / 4) = 5 (Condition 3: Satisfied).
  • Conditions met, update high = 6.

Conclusion:

• After Iteration 7, low and high will adjust such that low > high after the next step where low remains 7 and high becomes 6.
• The smallest value that satisfies all conditions is 7. This becomes the output of the binary search, representing the minimum maximum number that can be accommodated in both arrays under the given constraints.

Code

public class Solution {

  // Function to calculate the greatest common divisor (GCD)
  public long gcd(long a, long b) {
    if (b == 0) return a;
    return gcd(b, a % b);
  }

  // Function to minimize the maximum value in the two sets based on given conditions
  public int minimizeSet(
    long divisor1,
    long divisor2,
    long uniqueCnt1,
    long uniqueCnt2
  ) {
    long low = uniqueCnt1 + uniqueCnt2,
      high = divisor1 * divisor2 * uniqueCnt1 * uniqueCnt2; // Setting initial search bounds
    long lcm = (divisor1 * divisor2) / gcd(divisor1, divisor2); // Calculate the least common multiple (LCM)

    while (low <= high) {
      long mid = (low + high) / 2;
      long countBoth = mid / lcm; // Numbers divisible by both divisor1 and divisor2

      // Checking if the current mid can satisfy the conditions
      if (
        (mid - countBoth >= uniqueCnt1 + uniqueCnt2) &&
        (mid - (mid / divisor1) >= uniqueCnt1) &&
        (mid - (mid / divisor2) >= uniqueCnt2)
      ) {
        high = mid - 1; // Adjust high to find smaller max
      } else {
        low = mid + 1; // Adjust low to find feasible max
      }
    }
    return (int) low; // The minimum possible maximum value that satisfies the conditions
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Test Example 1
    System.out.println(
      "Output for Example 1: " + solution.minimizeSet(2, 3, 2, 2)
    ); // Expected Output: 4

    // Test Example 2
    System.out.println(
      "Output for Example 2: " + solution.minimizeSet(3, 4, 3, 4)
    ); // Expected Output: 7

    // Test Example 3
    System.out.println(
      "Output for Example 3: " + solution.minimizeSet(7, 10, 1, 1)
    ); // Expected Output: 2
  }
}

Complexity Analysis

Time Complexity

The time complexity of the minimizeSet function primarily revolves around the binary search mechanism used to narrow down the potential maximum integer:

• Binary Search: The loop runs as long as low is less than or equal to high. Each iteration approximately halves the search space, making the time complexity logarithmic. Given that the high is initialized to divisor1 * divisor2 * uniqueCnt1 * uniqueCnt2, the number of iterations is around , which is about 40.
• GCD Calculation: The time complexity of the Euclidean algorithm to compute the GCD is , where a and b are the inputs to the GCD function. However, this computation is done once and hence does not significantly impact the overall complexity.

Overall, the time complexity of the minimizeSet function is O(log(maxRange)), where maxRange is the difference between the initial high and low values, scaled logarithmically by the binary search.

Space Complexity

The space complexity of the solution is as the function utilizes a fixed amount of space for its variables (low, high, mid, countBoth, count1, count2, and lcm), and there are no dynamically sized data structures used.