2513. Minimize the Maximum of Two Arrays

Problem

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**.

  Example 1:

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.

Example 2:

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.

Example 3:

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 <= 105

• 1 <= uniqueCnt1, uniqueCnt2 < 109

• 2 <= uniqueCnt1 + uniqueCnt2 <= 109

Solution (Java)

class Solution {
    static public long gcd(int a, int b) { return b==0 ? a : gcd(b, a%b); }
    public int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
        long gcd=gcd(divisor1,divisor2), lcm=(long)divisor1*(long)divisor2/gcd;
        long divisible1=lcm/divisor1, divisible2=lcm/divisor2;
        long nondivisibleCommon = lcm - divisible1 - divisible2 + 1;
        long batches = (uniqueCnt1+uniqueCnt2)/(lcm-1), remainder = (uniqueCnt1+uniqueCnt2)%(lcm-1);
        long nondiv1=(divisible2-1)*batches, nondiv2=(divisible1-1)*batches, common=nondivisibleCommon*batches;
        nondiv1 += remainder/divisor2;
        nondiv2 += remainder/divisor1;
        common += (remainder-remainder/divisor1-remainder/divisor2);
        long answer = batches * lcm + remainder;
        if (nondiv1<=uniqueCnt1 && nondiv2<=uniqueCnt2) {
            return remainder==0 ? (int)answer - 1 : (int) answer;
        } else {
            long nondiv = nondiv1 >= uniqueCnt1 ? nondiv2 : nondiv1;
            long cnt = nondiv1 >= uniqueCnt1 ? uniqueCnt2 : uniqueCnt1;
            long divisor = nondiv1 >= uniqueCnt1 ? divisor2 : divisor1;
            long remain = cnt - nondiv - common;
            answer += remain/(divisor-1)*divisor;
            remain %= divisor-1;
            if (remain==0) {
                return  answer%divisor==0 ? (int)answer-1: (int)answer;
            } else if (answer%divisor + remain >= divisor) {
                return (int)answer + (int)remain + 1;
            } else {
                return (int)answer + (int)remain;
            }
        }
    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).