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 theminimum possible maximum integer that can be present in either array.

Examples

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 <= 10^5
• 1 <= uniqueCnt1, uniqueCnt2 < 109
• 2 <= uniqueCnt1 + uniqueCnt2 <= 10^9

Solution

Method 1 – Binary Search + Inclusion-Exclusion

Intuition

We need to pick uniqueCnt1 numbers not divisible by divisor1, and uniqueCnt2 numbers not divisible by divisor2, with no overlap. To minimize the maximum, we can use binary search to find the smallest number such that we can pick enough numbers for both arrays, using inclusion-exclusion to count valid numbers.

Approach

1. Use binary search for the answer between 1 and a large enough upper bound.
2. For a candidate maximum value, count:
   • Numbers not divisible by divisor1 (for arr1).
   • Numbers not divisible by divisor2 (for arr2).
   • Numbers not divisible by either (for overlap).
3. Use inclusion-exclusion to ensure no overlap between arr1 and arr2.
4. If we can pick enough numbers for both arrays, update answer and try lower; else, try higher.

Code

C++

class Solution {
public:
    int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
        auto lcm = [](int a, int b) { return a / std::gcd(a, b) * b; };
        int lo = 1, hi = 2e9, ans = -1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int both = mid / lcm(divisor1, divisor2);
            int only1 = mid / divisor1 - both;
            int only2 = mid / divisor2 - both;
            int neither = mid - mid / divisor1 - mid / divisor2 + both;
            if (only1 + neither >= uniqueCnt1 && only2 + neither >= uniqueCnt2 && only1 + only2 + neither >= uniqueCnt1 + uniqueCnt2) {
                ans = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return ans;
    }
};

Go

func gcd(a, b int) int { for b != 0 { a, b = b, a%b }; return a }
func lcm(a, b int) int { return a / gcd(a, b) * b }
func minimizeSet(divisor1, divisor2, uniqueCnt1, uniqueCnt2 int) int {
    lo, hi, ans := 1, 2_000_000_000, -1
    for lo <= hi {
        mid := lo + (hi-lo)/2
        both := mid / lcm(divisor1, divisor2)
        only1 := mid/divisor1 - both
        only2 := mid/divisor2 - both
        neither := mid - mid/divisor1 - mid/divisor2 + both
        if only1+neither >= uniqueCnt1 && only2+neither >= uniqueCnt2 && only1+only2+neither >= uniqueCnt1+uniqueCnt2 {
            ans = mid
            hi = mid - 1
        } else {
            lo = mid + 1
        }
    }
    return ans
}

Java

class Solution {
    public int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
        int lo = 1, hi = 2000000000, ans = -1;
        int lcm = lcm(divisor1, divisor2);
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int both = mid / lcm;
            int only1 = mid / divisor1 - both;
            int only2 = mid / divisor2 - both;
            int neither = mid - mid / divisor1 - mid / divisor2 + both;
            if (only1 + neither >= uniqueCnt1 && only2 + neither >= uniqueCnt2 && only1 + only2 + neither >= uniqueCnt1 + uniqueCnt2) {
                ans = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return ans;
    }
    private int lcm(int a, int b) {
        return a / gcd(a, b) * b;
    }
    private int gcd(int a, int b) {
        while (b != 0) {
            int t = b; b = a % b; a = t;
        }
        return a;
    }
}

Kotlin

class Solution {
    fun minimizeSet(divisor1: Int, divisor2: Int, uniqueCnt1: Int, uniqueCnt2: Int): Int {
        fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
        fun lcm(a: Int, b: Int): Int = a / gcd(a, b) * b
        var lo = 1
        var hi = 2_000_000_000
        var ans = -1
        val lcmVal = lcm(divisor1, divisor2)
        while (lo <= hi) {
            val mid = lo + (hi-lo)/2
            val both = mid / lcmVal
            val only1 = mid / divisor1 - both
            val only2 = mid / divisor2 - both
            val neither = mid - mid / divisor1 - mid / divisor2 + both
            if (only1 + neither >= uniqueCnt1 && only2 + neither >= uniqueCnt2 && only1 + only2 + neither >= uniqueCnt1 + uniqueCnt2) {
                ans = mid
                hi = mid - 1
            } else {
                lo = mid + 1
            }
        }
        return ans
    }
}

Python

def minimize_set(divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:
    from math import gcd
    def lcm(a: int, b: int) -> int:
        return a // gcd(a, b) * b
    lo, hi, ans = 1, 2_000_000_000, -1
    lcm_val = lcm(divisor1, divisor2)
    while lo <= hi:
        mid = (lo + hi) // 2
        both = mid // lcm_val
        only1 = mid // divisor1 - both
        only2 = mid // divisor2 - both
        neither = mid - mid // divisor1 - mid // divisor2 + both
        if only1 + neither >= uniqueCnt1 and only2 + neither >= uniqueCnt2 and only1 + only2 + neither >= uniqueCnt1 + uniqueCnt2:
            ans = mid
            hi = mid - 1
        else:
            lo = mid + 1
    return ans

Rust

impl Solution {
    pub fn minimize_set(divisor1: i32, divisor2: i32, unique_cnt1: i32, unique_cnt2: i32) -> i32 {
        fn gcd(a: i32, b: i32) -> i32 { if b == 0 { a } else { gcd(b, a % b) } }
        fn lcm(a: i32, b: i32) -> i32 { a / gcd(a, b) * b }
        let mut lo = 1;
        let mut hi = 2_000_000_000;
        let mut ans = -1;
        let lcm_val = lcm(divisor1, divisor2);
        while lo <= hi {
            let mid = lo + (hi-lo)/2;
            let both = mid / lcm_val;
            let only1 = mid / divisor1 - both;
            let only2 = mid / divisor2 - both;
            let neither = mid - mid / divisor1 - mid / divisor2 + both;
            if only1 + neither >= unique_cnt1 && only2 + neither >= unique_cnt2 && only1 + only2 + neither >= unique_cnt1 + unique_cnt2 {
                ans = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        ans
    }
}

TypeScript

class Solution {
    minimizeSet(divisor1: number, divisor2: number, uniqueCnt1: number, uniqueCnt2: number): number {
        function gcd(a: number, b: number): number { return b === 0 ? a : gcd(b, a % b); }
        function lcm(a: number, b: number): number { return a / gcd(a, b) * b; }
        let lo = 1, hi = 2_000_000_000, ans = -1;
        const lcmVal = lcm(divisor1, divisor2);
        while (lo <= hi) {
            const mid = Math.floor((lo + hi) / 2);
            const both = Math.floor(mid / lcmVal);
            const only1 = Math.floor(mid / divisor1) - both;
            const only2 = Math.floor(mid / divisor2) - both;
            const neither = mid - Math.floor(mid / divisor1) - Math.floor(mid / divisor2) + both;
            if (only1 + neither >= uniqueCnt1 && only2 + neither >= uniqueCnt2 && only1 + only2 + neither >= uniqueCnt1 + uniqueCnt2) {
                ans = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(log N)
  • Binary search over the answer range.
• 🧺 Space complexity: O(1)
  • Only a few variables used.