Skip to content

2513. Minimize the Maximum of Two Arrays 👍

  • Time: $O(\log 2^{31})$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
 public:
  int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
    const long divisorLcm = std::lcm(static_cast<long>(divisor1), divisor2);
    long l = 0;
    long r = INT_MAX;

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

    return l;
  }

 private:
  // Returns true if we can take uniqueCnt1 integers from [1..m] to arr1 and
  // take uniqueCnt2 integers from [1..m] to arr2.
  bool isPossible(long m, long divisorLcm, int divisor1, int divisor2,
                  int uniqueCnt1, int uniqueCnt2) {
    const long cnt1 = m - m / divisor1;
    const long cnt2 = m - m / divisor2;
    const long totalCnt = m - m / divisorLcm;
    return cnt1 >= uniqueCnt1 && cnt2 >= uniqueCnt2 &&
           totalCnt >= uniqueCnt1 + uniqueCnt2;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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;
  }

  // Returns true if we can take uniqueCnt1 integers from [1..m] to arr1 and
  // take uniqueCnt2 integers from [1..m] to arr2.
  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));
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def minimizeSet(self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:
    divisorLcm = math.lcm(divisor1, divisor2)
    l = 0
    r = 2**31 - 1

    # True if we can take uniqueCnt1 integers from [1..m] to arr1 and take
    # uniqueCnt2 integers from [1..m] to arr2.
    def isPossible(m: int) -> bool:
      cnt1 = m - m // divisor1
      cnt2 = m - m // divisor2
      totalCnt = m - m // divisorLcm
      return cnt1 >= uniqueCnt1 and cnt2 >= uniqueCnt2 and \
          totalCnt >= uniqueCnt1 + uniqueCnt2

    while l < r:
      m = (l + r) // 2
      if isPossible(m):
        r = m
      else:
        l = m + 1

    return l