import
java.util.*;
class
GFG {
public
static
int
makeSumEqual(
int
[] a,
int
[] b,
int
K,
int
M,
int
N)
{
int
sum1 =
0
;
int
sum2 =
0
;
for
(
int
el : a)
sum1 += el;
for
(
int
el : b)
sum2 += el;
int
diff = sum1 - sum2;
int
l1 =
0
, r1 = M -
1
;
int
l2 =
0
, r2 = N -
1
;
int
res =
0
;
Arrays.sort(a);
Arrays.sort(b);
while
(l1 <= r1 || l2 <= r2) {
if
(diff ==
0
) {
break
;
}
if
(diff >
0
) {
if
(l2 <= r2 && l1 <= r1) {
if
(K - b[l2] < a[r1] -
1
) {
int
sub = Math.min(
a[r1] -
1
, diff);
diff -= sub;
a[r1] -= sub;
r1--;
}
else
{
int
sub = Math.min(
K - b[l2], diff);
diff -= sub;
b[l2] += sub;
l2++;
}
}
else
if
(l1 <= r1) {
int
sub = Math.min(
a[r1] -
1
, diff);
diff -= sub;
a[r1] -= sub;
r1--;
}
else
{
int
sub = Math.min(
K - b[l2], diff);
diff -= sub;
b[l2] += sub;
l2++;
}
}
else
{
if
(l1 <= r1 && l2 <= r2) {
if
(K - a[l1]
< b[r2] -
1
) {
int
sub = Math.min(
b[r2] -
1
,
-
1
* diff);
diff += sub;
b[r2] -= sub;
r2--;
}
else
{
int
sub = Math.min(
K - a[l1],
-
1
* diff);
diff += sub;
a[l1] -= sub;
l1++;
}
}
else
if
(l2 <= r2) {
int
sub
= Math.min(
b[r2] -
1
,
-
1
* diff);
diff += sub;
b[r2] -= sub;
r2--;
}
else
{
int
sub = Math.min(
K - a[l1], diff);
diff += sub;
a[l1] += sub;
l1++;
}
}
res++;
}
if
(diff ==
0
)
return
res;
else
return
-
1
;
}
public
static
void
main(String[] args)
{
int
[] A = {
1
,
4
,
3
};
int
[] B = {
6
,
6
,
6
};
int
M = A.length;
int
N = B.length;
int
K =
6
;
System.out.println(
makeSumEqual(A, B, K,
M, N));
}
}
0 comments:
Post a Comment