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 uniqueCnt1distinct positive integers, each of which is not divisible by divisor1.
arr2 contains uniqueCnt2distinct 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.
Input: divisor1 =2, divisor2 =7, uniqueCnt1 =1, uniqueCnt2 =3Output: 4Explanation:
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 is4, we return it.
Input: divisor1 =3, divisor2 =5, uniqueCnt1 =2, uniqueCnt2 =1Output: 3Explanation:
Here arr1 =[1,2], and arr2 =[3] satisfy all conditions.Since the maximum value is3, we return it.
Input: divisor1 =2, divisor2 =4, uniqueCnt1 =8, uniqueCnt2 =2Output: 15Explanation:
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.
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.
classSolution {
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;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
funcgcd(a, bint) int { forb!=0 { a, b = b, a%b }; returna }
funclcm(a, bint) int { returna/gcd(a, b) *b }
funcminimizeSet(divisor1, divisor2, uniqueCnt1, uniqueCnt2int) int {
lo, hi, ans:=1, 2_000_000_000, -1forlo<=hi {
mid:=lo+ (hi-lo)/2both:=mid/lcm(divisor1, divisor2)
only1:=mid/divisor1-bothonly2:=mid/divisor2-bothneither:=mid-mid/divisor1-mid/divisor2+bothifonly1+neither>=uniqueCnt1&&only2+neither>=uniqueCnt2&&only1+only2+neither>=uniqueCnt1+uniqueCnt2 {
ans = midhi = mid-1 } else {
lo = mid+1 }
}
returnans}
classSolution {
publicintminimizeSet(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;
}
privateintlcm(int a, int b) {
return a / gcd(a, b) * b;
}
privateintgcd(int a, int b) {
while (b != 0) {
int t = b; b = a % b; a = t;
}
return a;
}
}
classSolution {
funminimizeSet(divisor1: Int, divisor2: Int, uniqueCnt1: Int, uniqueCnt2: Int): Int {
fungcd(a: Int, b: Int): Int = if (b ==0) a else gcd(b, a % b)
funlcm(a: Int, b: Int): Int = a / gcd(a, b) * b
var lo = 1var hi = 2_000_000_000
var ans = -1val lcmVal = lcm(divisor1, divisor2)
while (lo <= hi) {
val mid = lo + (hi-lo)/2val 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
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
defminimize_set(divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int) -> int:
from math import gcd
deflcm(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 -1else:
lo = mid +1return ans