Problem Description

You need to create two arrays arr1 and arr2 by adding positive integers to them according to specific rules:

Rules for arr1:

• Must contain exactly uniqueCnt1 distinct positive integers
• Each integer in arr1 must NOT be divisible by divisor1

Rules for arr2:

• Must contain exactly uniqueCnt2 distinct positive integers
• Each integer in arr2 must NOT be divisible by divisor2

Additional constraint:

• The two arrays must be completely disjoint (no integer can appear in both arrays)

Given the parameters divisor1, divisor2, uniqueCnt1, and uniqueCnt2, you need to find the minimum possible value of the maximum integer across both arrays.

In other words, if you optimally choose which positive integers to place in each array while satisfying all constraints, what's the smallest possible value for the largest number you'll need to use?

Example to clarify: If divisor1 = 2, divisor2 = 3, uniqueCnt1 = 1, uniqueCnt2 = 1:

• arr1 needs 1 number not divisible by 2 (could use 1, 3, 5, 7, ...)
• arr2 needs 1 number not divisible by 3 (could use 1, 2, 4, 5, ...)
• Since arrays can't share numbers, one optimal solution is arr1 = [1] and arr2 = [2]
• The maximum value used is 2, which would be the answer

Intuition

The key insight is that if we have a maximum value x, we can determine whether it's possible to construct valid arrays with all numbers ≤ x.

Think about what numbers are available up to x:

• For arr1: We can use all positive integers up to x that are NOT divisible by divisor1
• For arr2: We can use all positive integers up to x that are NOT divisible by divisor2

How many such numbers exist? If we have x total numbers:

• Numbers divisible by divisor1: x // divisor1
• Numbers NOT divisible by divisor1: x - (x // divisor1)
• Similarly, numbers NOT divisible by divisor2: x - (x // divisor2)

But there's a catch - some numbers might be valid for both arrays (not divisible by either divisor). Since we need disjoint arrays, we must carefully distribute these "flexible" numbers.

The critical observation is that numbers divisible by both divisor1 and divisor2 (i.e., divisible by lcm(divisor1, divisor2)) can't go in either array. So the total available numbers for both arrays combined is x minus the count of numbers divisible by the LCM.

This transforms our problem into a binary search question: "What's the smallest x such that we can fill both arrays?" We can check if a given x works by:

1. Counting how many valid numbers exist for arr1 only
2. Counting how many valid numbers exist for arr2 only
3. Counting how many numbers are valid for either array (flexible numbers)
4. Verifying we have enough numbers to satisfy both uniqueCnt1 and uniqueCnt2

Since we want the minimum possible maximum, binary search naturally finds the smallest x where this becomes feasible.

Learn more about Math and Binary Search patterns.

Solution Approach

The solution uses binary search to find the minimum possible maximum value. Here's how the implementation works:

Binary Search Setup: We use bisect_left to search for the smallest value x where our condition function f(x) returns True. The search range is set to range(10**10) which is large enough to cover all practical cases.

The Check Function f(x): For a given maximum value x, we calculate:

1. Count of valid numbers for arr1:

   • cnt1 = x // divisor1 * (divisor1 - 1) + x % divisor1
   • This formula counts numbers from 1 to x that are NOT divisible by divisor1
   • For every complete group of divisor1 numbers, we have (divisor1 - 1) valid ones
   • Plus any remaining numbers in the incomplete group (all are valid since they're less than divisor1)

2. Count of valid numbers for arr2:

   • cnt2 = x // divisor2 * (divisor2 - 1) + x % divisor2
   • Same logic as above but for divisor2

3. Count of numbers valid for either array:

   • divisor = lcm(divisor1, divisor2) (calculated once outside the function)
   • cnt = x // divisor * (divisor - 1) + x % divisor
   • This counts numbers NOT divisible by the LCM (numbers that could potentially go in either array)

Validation Conditions: The function returns True if all three conditions are met:

• cnt1 >= uniqueCnt1: Enough valid numbers exist for arr1
• cnt2 >= uniqueCnt2: Enough valid numbers exist for arr2
• cnt >= uniqueCnt1 + uniqueCnt2: Total available numbers (excluding those divisible by LCM) is sufficient for both arrays combined

The third condition is crucial - it ensures we have enough distinct numbers to fill both arrays without overlap, accounting for numbers that must go to specific arrays (those divisible by one divisor but not the other).

The binary search efficiently finds the smallest x where all conditions are satisfied, giving us the minimum possible maximum value.

Example Walkthrough

Let's walk through a concrete example with divisor1 = 2, divisor2 = 3, uniqueCnt1 = 3, uniqueCnt2 = 2.

We need:

• arr1: 3 distinct numbers not divisible by 2 (odd numbers)
• arr2: 2 distinct numbers not divisible by 3
• The arrays must be disjoint

Binary Search Process:

Let's check if x = 7 works:

1. Count valid numbers for arr1 (not divisible by 2):

   • Numbers 1-7: {1, 2, 3, 4, 5, 6, 7}
   • Not divisible by 2: {1, 3, 5, 7} → 4 numbers
   • Using formula: 7 // 2 * (2-1) + 7 % 2 = 3 * 1 + 1 = 4 ✓

2. Count valid numbers for arr2 (not divisible by 3):

   • Not divisible by 3: {1, 2, 4, 5, 7} → 5 numbers
   • Using formula: 7 // 3 * (3-1) + 7 % 3 = 2 * 2 + 1 = 5 ✓

3. Count total available (not divisible by lcm(2,3) = 6):

   • Not divisible by 6: {1, 2, 3, 4, 5, 7} → 6 numbers
   • Using formula: 7 // 6 * (6-1) + 7 % 6 = 1 * 5 + 1 = 6 ✓

Validation:

• cnt1 = 4 >= 3 ✓ (enough odd numbers for arr1)
• cnt2 = 5 >= 2 ✓ (enough non-multiples of 3 for arr2)
• cnt = 6 >= 3 + 2 = 5 ✓ (enough total distinct numbers)

All conditions met! But let's verify x = 6 doesn't work:

For x = 6:

• Valid for arr1: {1, 3, 5} → 3 numbers
• Valid for arr2: {1, 2, 4, 5} → 4 numbers
• Total available: {1, 2, 3, 4, 5} → 5 numbers (6 is divisible by lcm=6)

Conditions: 3 >= 3 ✓, 4 >= 2 ✓, 5 >= 5 ✓

Actually x = 6 works! Let's check x = 5:

• Valid for arr1: {1, 3, 5} → 3 numbers
• Valid for arr2: {1, 2, 4, 5} → 4 numbers
• Total available: {1, 2, 3, 4, 5} → 5 numbers

Conditions work, so let's try x = 4:

• Valid for arr1: {1, 3} → 2 numbers
• Valid for arr2: {1, 2, 4} → 3 numbers
• Total available: {1, 2, 3, 4} → 4 numbers

Conditions: 2 >= 3 ✗ FAILS!

Therefore, the minimum x is 5. One valid assignment would be:

• arr1 = [1, 3, 5] (3 odd numbers)
• arr2 = [2, 4] (2 numbers not divisible by 3)

The maximum value used is 5, which is our answer.

Solution Implementation

Time and Space Complexity

Time Complexity: O(log(10^10) × log(divisor1 × divisor2))

The binary search using bisect_left searches in the range [0, 10^10), which takes O(log(10^10)) iterations. For each iteration, the function f(x) is called, which performs:

• Division and modulo operations with divisor1, divisor2, and divisor (LCM of divisor1 and divisor2): O(1)
• The LCM calculation lcm(divisor1, divisor2) involves computing the GCD using Euclidean algorithm: O(log(min(divisor1, divisor2)))

Since the LCM is calculated once outside the binary search, and assuming the LCM function internally uses GCD with time complexity O(log(divisor1 × divisor2)), the overall time complexity is O(log(divisor1 × divisor2) + log(10^10)), which simplifies to O(log(10^10)) as the dominant term.

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space for:

• Variables cnt1, cnt2, cnt in function f
• Variable divisor to store the LCM
• The binary search mechanism in bisect_left uses O(1) space as it works with indices

The range(10^10) object is a generator that doesn't create the entire list in memory, so it contributes O(1) space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Counting of Available Numbers

The Problem: A common mistake is incorrectly calculating how many numbers from 1 to x are not divisible by a given divisor. The naive approach might try to iterate and count, or use an incorrect formula like x - x // divisor which doesn't account for the pattern correctly.

Why It Happens: The formula x - (x // divisor) seems intuitive - total numbers minus divisible numbers. However, this is exactly what we want! The confusion often comes from overthinking or trying to use modular arithmetic incorrectly, such as x // divisor * (divisor - 1) + x % divisor which would count incorrectly.

The Solution: Use the straightforward formula: available = x - (x // divisor)

• This directly counts non-divisible numbers
• For example, with x = 10 and divisor = 3: we have 10 - (10//3) = 10 - 3 = 7 numbers not divisible by 3 (which are: 1, 2, 4, 5, 7, 8, 10)

Pitfall 2: Forgetting the Disjoint Constraint

The Problem: Some solutions only check if there are enough valid numbers for each array independently (available_for_set1 >= uniqueCnt1 and available_for_set2 >= uniqueCnt2) but forget to verify that we have enough total unique numbers to fill both arrays without overlap.

Why It Happens: It's easy to focus on each array's individual requirements and miss the global constraint that no number can appear in both arrays.

The Solution: Always include the third condition: available_for_both >= uniqueCnt1 + uniqueCnt2

• This ensures the total pool of available numbers (those not divisible by LCM) is large enough
• Numbers divisible by only one divisor are forced into one specific array
• Numbers divisible by neither can go in either array, providing flexibility

Pitfall 3: Integer Overflow with LCM Calculation

The Problem: When calculating lcm(divisor1, divisor2), the result can be very large, potentially causing integer overflow in languages with fixed integer sizes or leading to performance issues.

Why It Happens: LCM can grow quickly. For example, if divisor1 = 10^5 and divisor2 = 10^5 - 1, the LCM could be close to 10^10.

The Solution:

• In Python, this is less of an issue due to arbitrary precision integers
• For other languages, use careful overflow checking or long/BigInteger types
• Consider using the formula: lcm(a, b) = a * b // gcd(a, b) with GCD calculation to avoid intermediate overflow
• Set appropriate upper bounds for binary search based on problem constraints

Pitfall 4: Inefficient Binary Search Bounds

The Problem: Using an unnecessarily large search range like range(10**10) when a smaller bound would suffice, leading to more iterations than needed.

Why It Happens: Without analyzing the problem constraints, it's tempting to use a "safe" large number that will definitely contain the answer.

The Solution: Calculate a tighter upper bound based on the problem:

# The answer is at most the sum of counts plus some buffer for divisibility constraints
upper_bound = (uniqueCnt1 + uniqueCnt2) * max(divisor1, divisor2)
return bisect_left(range(upper_bound + 1), True, key=can_form_sets)

This reduces the number of binary search iterations while still guaranteeing correctness.