LeetCode Problem 2513

Difficulty: 🟡 Medium
Topics: Math, Binary Search, Number Theory

Solution

LeetCode 2513 - Minimize the Maximum of Two Arrays

Problem Understanding

The problem gives us two empty arrays, arr1 and arr2, and asks us to fill them with positive integers under several constraints.

The first array, arr1, must contain exactly uniqueCnt1 distinct positive integers, and none of those integers can be divisible by divisor1.

The second array, arr2, must contain exactly uniqueCnt2 distinct positive integers, and none of those integers can be divisible by divisor2.

Additionally, the two arrays must be completely disjoint. A number chosen for one array cannot appear in the other.

Our goal is to minimize the largest number used across both arrays. In other words, if the maximum value appearing in either array is x, we want the smallest possible such x.

The input consists of four integers:

• divisor1, the divisibility restriction for arr1
• divisor2, the divisibility restriction for arr2
• uniqueCnt1, the required size of arr1
• uniqueCnt2, the required size of arr2

The output is a single integer representing the minimum possible maximum value that allows both arrays to be constructed successfully.

The constraints are extremely important:

• uniqueCnt1 and uniqueCnt2 can each be close to 10^9
• Their sum can also be close to 10^9

These limits immediately rule out any simulation-based solution that explicitly constructs the arrays. We need a mathematical approach.

An important observation is that we never actually need to know the exact contents of the arrays. We only need to know whether a certain maximum value x provides enough valid numbers to satisfy both arrays simultaneously.

Several edge cases are important:

• divisor1 and divisor2 may share factors
• One divisor may divide the other
• The required counts may be extremely large
• Many numbers may be unusable for one or both arrays
• Some numbers may be valid for both arrays, while others are valid for only one

The disjointness requirement is the trickiest part of the problem because a number that works for both arrays can only be assigned once.

Approaches

Brute Force Approach

A brute force solution would try increasing maximum values one by one.

For each candidate maximum x, we could enumerate all numbers from 1 to x, classify which numbers are usable for arr1, which are usable for arr2, and then attempt to distribute them while keeping the arrays disjoint.

This works because eventually we would find the smallest valid x.

However, this approach is far too slow. The maximum answer can become very large, potentially exceeding billions. Iterating through every integer and explicitly constructing sets would be computationally infeasible.

Even checking a single candidate value naively would cost O(x), which is impossible for the given constraints.

Key Insight

The key observation is that we do not need to explicitly build the arrays.

Instead, for a candidate maximum value x, we only need to count:

1. How many numbers from 1 to x are valid for arr1
2. How many numbers from 1 to x are valid for arr2
3. How many numbers are valid for at least one array

These counts can be computed mathematically using divisibility.

For example:

• Numbers not divisible by divisor1:

x - x // divisor1

• Numbers not divisible by divisor2:

x - x // divisor2

The tricky part is counting numbers usable by at least one array.

A number is unusable only if it is divisible by both divisors simultaneously. That means it is divisible by:

$$\text{lcm}(divisor1, divisor2)$$

So the count of numbers usable by at least one array is:

$$x - x // \text{lcm}(divisor1, divisor2)$$

Now the problem becomes a decision problem:

"Can we satisfy both arrays using numbers up to x?"

This property is monotonic:

• If x works, then every larger value also works.
• If x does not work, then every smaller value also fails.

That monotonic behavior makes binary search the perfect tool.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(x) per check	O(x)	Explicitly constructs or simulates valid numbers
Optimal	O(log(answer))	O(1)	Uses counting mathematics with binary search

Algorithm Walkthrough

Step 1: Compute the Least Common Multiple

We compute:

$$lcm = \frac{divisor1 \times divisor2}{gcd(divisor1, divisor2)}$$

The LCM lets us count numbers divisible by both divisors simultaneously.

Step 2: Binary Search Over the Answer

We search for the smallest maximum value x.

The search range is:

• Left boundary: 1
• Right boundary: a sufficiently large number such as 10^18

We use a large upper bound because the constraints allow very large answers.

Step 3: Count Numbers Valid for arr1

For a candidate mid:

$$count1 = mid - mid // divisor1$$

These are the numbers from 1 to mid that are not divisible by divisor1.

They are eligible for arr1.

Step 4: Count Numbers Valid for arr2

Similarly:

$$count2 = mid - mid // divisor2$$

These are eligible for arr2.

Step 5: Count Numbers Usable Overall

Some numbers may work for both arrays.

The only unusable numbers are those divisible by both divisors simultaneously.

That count is:

$$mid // lcm$$

So the count of numbers usable by at least one array is:

$$total = mid - mid // lcm$$

Step 6: Check Feasibility

A candidate mid is valid if all three conditions hold:

$$count1 \ge uniqueCnt1$$

$$count2 \ge uniqueCnt2$$

$$total \ge uniqueCnt1 + uniqueCnt2$$

The third condition guarantees that we can assign distinct numbers across both arrays without overlap.

Step 7: Adjust Binary Search

If mid is feasible:

• Store it as a possible answer
• Search smaller values

Otherwise:

• Search larger values

Step 8: Return the Smallest Valid Value

The binary search eventually converges to the minimum feasible maximum integer.

Why it works

The correctness relies on monotonicity.

If a maximum value x provides enough usable numbers for both arrays, then any value larger than x will also work because it only introduces more candidate integers.

The counting formulas correctly determine how many integers satisfy each divisibility condition. The combined count using the LCM guarantees that enough distinct integers exist overall to keep the arrays disjoint.

Therefore, binary search finds the smallest feasible maximum value.

Python Solution

from math import gcd

class Solution:
    def minimizeSet(
        self,
        divisor1: int,
        divisor2: int,
        uniqueCnt1: int,
        uniqueCnt2: int
    ) -> int:

        lcm = divisor1 * divisor2 // gcd(divisor1, divisor2)

        left = 1
        right = 10**18

        while left < right:
            mid = (left + right) // 2

            count1 = mid - mid // divisor1
            count2 = mid - mid // divisor2
            total = mid - mid // lcm

            if (
                count1 >= uniqueCnt1 and
                count2 >= uniqueCnt2 and
                total >= uniqueCnt1 + uniqueCnt2
            ):
                right = mid
            else:
                left = mid + 1

        return left

The implementation starts by computing the least common multiple using the greatest common divisor.

The binary search maintains a search space containing all possible answers. At each iteration, the midpoint is tested for feasibility.

The variables count1 and count2 represent how many integers up to mid are valid for each array individually. The variable total represents how many integers are usable overall.

The feasibility condition ensures:

• arr1 can be filled
• arr2 can be filled
• The arrays can remain disjoint

If all conditions are satisfied, we try smaller values because we want the minimum possible maximum. Otherwise, we increase the search range.

The loop terminates when left == right, which is the smallest feasible value.

Go Solution

package main

func gcd(a int64, b int64) int64 {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func minimizeSet(divisor1 int, divisor2 int, uniqueCnt1 int, uniqueCnt2 int) int {
	d1 := int64(divisor1)
	d2 := int64(divisor2)
	u1 := int64(uniqueCnt1)
	u2 := int64(uniqueCnt2)

	lcm := d1 * d2 / gcd(d1, d2)

	left := int64(1)
	right := int64(1e18)

	for left < right {
		mid := (left + right) / 2

		count1 := mid - mid/d1
		count2 := mid - mid/d2
		total := mid - mid/lcm

		if count1 >= u1 &&
			count2 >= u2 &&
			total >= u1+u2 {
			right = mid
		} else {
			left = mid + 1
		}
	}

	return int(left)
}

The Go implementation is structurally identical to the Python version, but it uses int64 everywhere to avoid integer overflow.

This is especially important because the binary search upper bound is 10^18, which exceeds the capacity of standard 32-bit integers.

The custom gcd function uses the Euclidean algorithm.

Worked Examples

Example 1

Input:

divisor1 = 2
divisor2 = 7
uniqueCnt1 = 1
uniqueCnt2 = 3

Binary Search Checks

mid	count1	count2	total	Valid?
4	2	4	4	Yes
2	1	2	2	No
3	2	3	3	No

At mid = 4:

• Numbers not divisible by 2: 1,3
• Numbers not divisible by 7: 1,2,3,4
• Total usable numbers: 1,2,3,4

We can assign:

• arr1 = [1]
• arr2 = [2,3,4]

The answer is 4.

Example 2

Input:

divisor1 = 3
divisor2 = 5
uniqueCnt1 = 2
uniqueCnt2 = 1

Check mid = 3

Value	Result
count1	2
count2	3
total	3

Numbers up to 3:

• Valid for arr1: 1,2
• Valid for arr2: 1,2,3

We can assign:

• arr1 = [1,2]
• arr2 = [3]

The answer is 3.

Example 3

Input:

divisor1 = 2
divisor2 = 4
uniqueCnt1 = 8
uniqueCnt2 = 2

Check mid = 15

Value	Result
count1	8
count2	12
total	12

Numbers not divisible by 2:

1,3,5,7,9,11,13,15

Numbers not divisible by 4 include many even numbers such as:

2,6

We can assign:

• arr1 = [1,3,5,7,9,11,13,15]
• arr2 = [2,6]

The answer is 15.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log(answer))	Binary search over the numeric range
Space	O(1)	Only constant extra variables are used

The binary search range is extremely large, but binary search reduces it exponentially. Since the upper bound is approximately 10^18, the algorithm performs around 60 iterations.

Each iteration performs only constant-time arithmetic operations, making the solution highly efficient even for the largest constraints.

Test Cases

sol = Solution()

# Provided examples
assert sol.minimizeSet(2, 7, 1, 3) == 4  # Example 1
assert sol.minimizeSet(3, 5, 2, 1) == 3  # Example 2
assert sol.minimizeSet(2, 4, 8, 2) == 15  # Example 3

# Small basic cases
assert sol.minimizeSet(2, 3, 1, 1) == 2  # Minimal non-overlapping assignment
assert sol.minimizeSet(2, 3, 2, 2) == 4  # Small balanced counts

# Same divisors
assert sol.minimizeSet(2, 2, 1, 1) == 3  # Must avoid overlap completely
assert sol.minimizeSet(5, 5, 3, 4) == 8  # Shared restriction

# One divisor divides the other
assert sol.minimizeSet(2, 4, 3, 2) == 5  # Nested divisibility
assert sol.minimizeSet(3, 6, 4, 3) == 8  # One divisor multiple of another

# Large counts
assert sol.minimizeSet(2, 3, 1000000, 1000000) > 0  # Stress test
assert sol.minimizeSet(99991, 99989, 100000000, 100000000) > 0  # Very large values

# Prime divisors
assert sol.minimizeSet(7, 11, 5, 5) == 10  # Sparse exclusions

# Large overlap pressure
assert sol.minimizeSet(2, 2, 100, 100) == 399  # Need many distinct odd numbers

print("All tests passed!")

Test Summary

Test	Why
(2,7,1,3)	Verifies example 1
(3,5,2,1)	Verifies example 2
(2,4,8,2)	Verifies example 3
Same divisors	Tests overlap handling
One divisor multiple of another	Tests LCM correctness
Large counts	Stress tests binary search
Large prime divisors	Tests sparse exclusion patterns
Heavy overlap pressure	Ensures distinctness logic works

Edge Cases

Case 1: Both Divisors Are Equal

If divisor1 == divisor2, then both arrays reject exactly the same numbers.

This creates maximum competition for usable integers because every valid number is eligible for both arrays. A buggy implementation might only verify the individual counts and forget that the arrays must remain disjoint.

The implementation avoids this issue with the condition:

$$total \ge uniqueCnt1 + uniqueCnt2$$

This guarantees enough distinct usable numbers overall.

Case 2: One Divisor Is a Multiple of the Other

For example:

divisor1 = 2
divisor2 = 4

Every number divisible by 4 is also divisible by 2.

This can easily break incorrect inclusion-exclusion logic.

The implementation handles this safely by using the least common multiple. The LCM correctly identifies numbers divisible by both divisors simultaneously.

Case 3: Extremely Large Counts

The counts can approach 10^9, and the answer itself can become very large.

A naive implementation that constructs arrays or iterates through numbers would time out or run out of memory.

The solution avoids all explicit construction and uses only arithmetic counting formulas, allowing it to scale efficiently even for the largest inputs.