Description#
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.
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 <= 1051 <= uniqueCnt1, uniqueCnt2 < 1092 <= uniqueCnt1 + uniqueCnt2 <= 109
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution:
def minimizeSet(
self, divisor1: int, divisor2: int, uniqueCnt1: int, uniqueCnt2: int
) -> int:
def f(x):
cnt1 = x // divisor1 * (divisor1 - 1) + x % divisor1
cnt2 = x // divisor2 * (divisor2 - 1) + x % divisor2
cnt = x // divisor * (divisor - 1) + x % divisor
return (
cnt1 >= uniqueCnt1
and cnt2 >= uniqueCnt2
and cnt >= uniqueCnt1 + uniqueCnt2
)
divisor = lcm(divisor1, divisor2)
return bisect_left(range(10**10), True, key=f)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
long divisor = lcm(divisor1, divisor2);
long left = 1, right = 10000000000L;
while (left < right) {
long mid = (left + right) >> 1;
long cnt1 = mid / divisor1 * (divisor1 - 1) + mid % divisor1;
long cnt2 = mid / divisor2 * (divisor2 - 1) + mid % divisor2;
long cnt = mid / divisor * (divisor - 1) + mid % divisor;
if (cnt1 >= uniqueCnt1 && cnt2 >= uniqueCnt2 && cnt >= uniqueCnt1 + uniqueCnt2) {
right = mid;
} else {
left = mid + 1;
}
}
return (int) left;
}
private long lcm(int a, int b) {
return (long) a * b / gcd(a, b);
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
long left = 1, right = 1e10;
long divisor = lcm((long) divisor1, (long) divisor2);
while (left < right) {
long mid = (left + right) >> 1;
long cnt1 = mid / divisor1 * (divisor1 - 1) + mid % divisor1;
long cnt2 = mid / divisor2 * (divisor2 - 1) + mid % divisor2;
long cnt = mid / divisor * (divisor - 1) + mid % divisor;
if (cnt1 >= uniqueCnt1 && cnt2 >= uniqueCnt2 && cnt >= uniqueCnt1 + uniqueCnt2) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| func minimizeSet(divisor1 int, divisor2 int, uniqueCnt1 int, uniqueCnt2 int) int {
divisor := lcm(divisor1, divisor2)
left, right := 1, 10000000000
for left < right {
mid := (left + right) >> 1
cnt1 := mid/divisor1*(divisor1-1) + mid%divisor1
cnt2 := mid/divisor2*(divisor2-1) + mid%divisor2
cnt := mid/divisor*(divisor-1) + mid%divisor
if cnt1 >= uniqueCnt1 && cnt2 >= uniqueCnt2 && cnt >= uniqueCnt1+uniqueCnt2 {
right = mid
} else {
left = mid + 1
}
}
return left
}
func lcm(a, b int) int {
return a * b / gcd(a, b)
}
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}
|
