Minimize the Maximum of Two Arrays - Practice Coding Problems

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.

Input & Output

Example 1 — Basic Case

$ Input: divisor1 = 2, divisor2 = 3, uniqueCnt1 = 1, uniqueCnt2 = 1

› Output: 3

💡 Note: We can put 1 in arr1 (not divisible by 2) and 2 in arr2 (not divisible by 3). The maximum is 3, but we only use up to 2, so we need to check if 2 works. With maxVal=2: arr1 can use {1}, arr2 can use {1} but 1 is already in arr1. So maxVal=3: arr1 can use {1,3}, take 1. arr2 can use {1,2}, take 2. Maximum element is 2, but minimum possible maximum is 3.

Example 2 — Larger Requirements

$ Input: divisor1 = 3, divisor2 = 5, uniqueCnt1 = 2, uniqueCnt2 = 1

› Output: 4

💡 Note: For maxVal=4: Numbers not divisible by 3: {1,2,4}. Numbers not divisible by 5: {1,2,3,4}. arr1 needs 2 elements from {1,2,4}, take {1,2}. arr2 needs 1 element from {1,2,3,4} excluding {1,2}, can take {3}. All requirements satisfied with maximum 4.

Example 3 — Same Divisors

$ Input: divisor1 = 2, divisor2 = 2, uniqueCnt1 = 1, uniqueCnt2 = 1

› Output: 3

💡 Note: Both arrays need elements not divisible by 2. Available: {1,3,5,...}. arr1 takes 1, arr2 takes 3. Minimum maximum is 3.

Constraints

2 ≤ divisor1, divisor2 ≤ 10⁵
1 ≤ uniqueCnt1, uniqueCnt2 ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

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

Process

Find minimum maximum allowing both arrays to be filled

Output

Minimum possible maximum = 3

Key Takeaway

🎯 Key Insight: Binary search on the maximum value while using inclusion-exclusion to count valid numbers efficiently

Asked in

G Google 25 M Microsoft 18 a Amazon 15

The key insight is to use binary search on the answer space combined with inclusion-exclusion principle to count valid numbers. We search for the minimum possible maximum value where both arrays can be filled with required counts. Best approach is Binary Search on Answer with Time: O(log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Linear Search	O(n)	O(1)	Try each possible maximum value from 1 upward until we find one that works
Binary Search on Answer	O(log n)	O(1)	Binary search on the maximum value to find the minimum feasible answer

Brute Force Linear Search — Algorithm Steps

Start with maximum = 1
Count valid numbers for arr1 (not divisible by divisor1)
Count valid numbers for arr2 (not divisible by divisor2)
Check if arrays can be filled without overlap
If successful, return current maximum; otherwise increment

Visualization

Tap to expand

Step-by-Step Walkthrough

Try maxVal = 1

Count valid numbers for each array

Check if feasible

See if arrays can be filled without overlap

Increment and retry

If not feasible, try next value

Code -

solution.c — C

#include <stdio.h>
#include <stdbool.h>

long long gcd(long long a, long long b) {
    while (b != 0) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

long long lcm(long long a, long long b) {
    return a * b / gcd(a, b);
}

long long min(long long a, long long b) {
    return a < b ? a : b;
}

bool canFill(int maxVal, int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
    long long validFor1 = maxVal - maxVal / divisor1;
    long long validFor2 = maxVal - maxVal / divisor2;
    long long lcmVal = lcm(divisor1, divisor2);
    long long validForBoth = maxVal - maxVal / divisor1 - maxVal / divisor2 + maxVal / lcmVal;
    
    long long used1 = min(uniqueCnt1, validFor1);
    long long remaining1 = uniqueCnt1 - used1;
    
    long long fromBoth1 = min(remaining1, validForBoth);
    long long validForBothRemaining = validForBoth - fromBoth1;
    used1 += fromBoth1;
    
    if (used1 < uniqueCnt1) {
        return false;
    }
    
    long long used2 = min(uniqueCnt2, validFor2);
    long long remaining2 = uniqueCnt2 - used2;
    
    long long fromBoth2 = min(remaining2, validForBothRemaining);
    used2 += fromBoth2;
    
    return used2 >= uniqueCnt2;
}

int solution(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
    int maxVal = 1;
    while (!canFill(maxVal, divisor1, divisor2, uniqueCnt1, uniqueCnt2)) {
        maxVal++;
    }
    return maxVal;
}

int main() {
    int divisor1, divisor2, uniqueCnt1, uniqueCnt2;
    scanf("%d\n%d\n%d\n%d", &divisor1, &divisor2, &uniqueCnt1, &uniqueCnt2);
    printf("%d\n", solution(divisor1, divisor2, uniqueCnt1, uniqueCnt2));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Linear search through possible maximum values, where n is the answer

✓ Linear Growth

Space Complexity

O(1)

Only uses constant extra variables for counting

✓ Linear Space

12.5K Views

Medium Frequency

~25 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Linear Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler