Minimize the Maximum of Two Arrays

Medium
1319.

Minimize the Maximum of Two Arrays

Minimize the Maximum of Two Arrays is a medium coding problem on math, binary search and number theory, asked in Amazon and Google interviews.

Fill two initially empty arrays arr1 and arr2 with positive integers so that:

  • arr1 holds uniqueCnt1 distinct integers, none of them divisible by divisor1;
  • arr2 holds uniqueCnt2 distinct integers, none of them divisible by divisor2;
  • no integer appears in both arrays.

Return the smallest possible value of the largest integer used in either array.

Example 1

Input
divisor1 = 2, divisor2 = 3, uniqueCnt1 = 2, uniqueCnt2 = 2
Output
4
Explanation
arr1 = [1, 3] (odd numbers) and arr2 = [2, 4] (not multiples of 3).

Example 2

Input
divisor1 = 3, divisor2 = 5, uniqueCnt1 = 2, uniqueCnt2 = 1
Output
3
Explanation
arr1 = [1, 2], arr2 = [3].

Example 3

Input
divisor1 = 2, divisor2 = 2, uniqueCnt1 = 500000000, uniqueCnt2 = 500000000
Output
1999999999
Explanation
Both arrays need odd numbers, 10^9 of them in total.

Constraints

  • 2 <= divisor1, divisor2 <= 10^5
  • 1 <= uniqueCnt1, uniqueCnt2 < 10^9
  • 2 <= uniqueCnt1 + uniqueCnt2 <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} divisor1
 * @param {number} divisor2
 * @param {number} uniqueCnt1
 * @param {number} uniqueCnt2
 * @return {number}
 */
var minimizeSet = function(divisor1, divisor2, uniqueCnt1, uniqueCnt2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimize the Maximum of Two Arrays — Problem & Solution

Minimize the Maximum of Two Arrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimize the Maximum of Two Arrays is a medium coding problem on math, binary search and number theory, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Math, Binary Search, Number Theory
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Fill two initially empty arrays arr1 and arr2 with positive integers so that:

  • arr1 holds uniqueCnt1 distinct integers, none of them divisible by divisor1;
  • arr2 holds uniqueCnt2 distinct integers, none of them divisible by divisor2;
  • no integer appears in both arrays.

Return the smallest possible value of the largest integer used in either array.

Example 1

Input: divisor1 = 2, divisor2 = 3, uniqueCnt1 = 2, uniqueCnt2 = 2
Output: 4
Explanation: arr1 = [1, 3] (odd numbers) and arr2 = [2, 4] (not multiples of 3).

Example 2

Input: divisor1 = 3, divisor2 = 5, uniqueCnt1 = 2, uniqueCnt2 = 1
Output: 3
Explanation: arr1 = [1, 2], arr2 = [3].

Example 3

Input: divisor1 = 2, divisor2 = 2, uniqueCnt1 = 500000000, uniqueCnt2 = 500000000
Output: 1999999999
Explanation: Both arrays need odd numbers, 10^9 of them in total.

Constraints

  • 2 <= divisor1, divisor2 <= 10^5
  • 1 <= uniqueCnt1, uniqueCnt2 < 10^9
  • 2 <= uniqueCnt1 + uniqueCnt2 <= 10^9

Hints for Minimize the Maximum of Two Arrays

  1. Hint 1

    If the arrays can be filled using numbers up to x, they can also be filled up to x + 1 — so binary search on x.

  2. Hint 2

    Among 1..x: x - x/divisor1 numbers are allowed in arr1, x - x/divisor2 in arr2, and x - x/lcm in at least one of them.

  3. Hint 3

    x is enough exactly when all three counts reach uniqueCnt1, uniqueCnt2 and uniqueCnt1 + uniqueCnt2 respectively.

How to solve Minimize the Maximum of Two Arrays

Feasibility is monotone in the largest allowed value x, and it reduces to three counting inequalities. Binary search for the smallest x that satisfies all three.

Approach

  1. Let L = lcm(divisor1, divisor2) = divisor1 / gcd · divisor2 (up to 10^10, so use 64 bits).
  2. For a candidate x, require x - floor(x/divisor1) >= uniqueCnt1, x - floor(x/divisor2) >= uniqueCnt2 and x - floor(x/L) >= uniqueCnt1 + uniqueCnt2.
  3. Binary search x over [1, 2·10^9] for the smallest value meeting all three.

Why it works

Split 1..x into four groups: multiples of divisor2 only (usable only by arr1), multiples of divisor1 only (only by arr2), multiples of neither (either array) and multiples of both (neither). arr1 takes what it can from its private group and the rest from the shared one, arr2 likewise, so a filling exists exactly when each array has enough candidates on its own and both together have enough non-multiples of L — the three inequalities. Each count grows with x, so feasibility is monotone and binary search is valid. The answer never exceeds 2·10^9 - 1 (the worst case is both divisors 2).

Complexity

  • Time — O(log(2·10^9))
  • Space — O(1)

Pitfalls

  • Checking only the two per-array conditions ignores that the arrays compete for the same numbers.
  • lcm can reach 10^10 and uniqueCnt1 + uniqueCnt2 is near 10^9 — keep the arithmetic in 64 bits.
  • Use lcm, not divisor1 · divisor2, when the divisors share a factor (e.g. 2 and 4).

Reference solution

Python

import math

def minimizeSet(divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:
    lcm = divisor1 // math.gcd(divisor1, divisor2) * divisor2
    lo, hi = 1, 2 * 10 ** 9
    while lo < hi:
        mid = (lo + hi) // 2
        if (mid - mid // divisor1 >= uniqueCnt1 and mid - mid // divisor2 >= uniqueCnt2
                and mid - mid // lcm >= uniqueCnt1 + uniqueCnt2):
            hi = mid
        else:
            lo = mid + 1
    return lo

Java

public static int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
    long a = divisor1, b = divisor2;
    while (b != 0) { long t = a % b; a = b; b = t; }
    long lcm = divisor1 / a * divisor2;
    long need = (long) uniqueCnt1 + uniqueCnt2;
    long lo = 1, hi = 2000000000L;
    while (lo < hi) {
        long mid = (lo + hi) / 2;
        if (mid - mid / divisor1 >= uniqueCnt1 && mid - mid / divisor2 >= uniqueCnt2 && mid - mid / lcm >= need) hi = mid;
        else lo = mid + 1;
    }
    return (int) lo;
}

C++

int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
    long long a = divisor1, b = divisor2;
    while (b != 0) { long long t = a % b; a = b; b = t; }
    long long lcm = divisor1 / a * divisor2;
    long long need = (long long) uniqueCnt1 + uniqueCnt2;
    long long lo = 1, hi = 2000000000LL;
    while (lo < hi) {
        long long mid = (lo + hi) / 2;
        if (mid - mid / divisor1 >= uniqueCnt1 && mid - mid / divisor2 >= uniqueCnt2 && mid - mid / lcm >= need) hi = mid;
        else lo = mid + 1;
    }
    return (int) lo;
}

JavaScript

var minimizeSet = function(divisor1, divisor2, uniqueCnt1, uniqueCnt2) {
    var a = divisor1, b = divisor2;
    while (b !== 0) { var t = a % b; a = b; b = t; }
    var lcm = divisor1 / a * divisor2;
    var lo = 1, hi = 2000000000;
    while (lo < hi) {
        var mid = Math.floor((lo + hi) / 2);
        var ok = mid - Math.floor(mid / divisor1) >= uniqueCnt1 &&
            mid - Math.floor(mid / divisor2) >= uniqueCnt2 &&
            mid - Math.floor(mid / lcm) >= uniqueCnt1 + uniqueCnt2;
        if (ok) hi = mid; else lo = mid + 1;
    }
    return lo;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Binary Search