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