Make A and B equal | CodeChef Solution | Problem Code: MAKEABEQUAL

 

Problem



Chef is given two arrays A and B of length N each.

In one operation Chef can choose one element of A and one element of B and increase them by 1.

More formally: Chef can pick two integers i, j (1\le i, j \le N) and increment A_i and B_j by 1.

Determine the minimum number of operations required to make A and B equal.

Output -1 if it is not possible to make A and B equal.

Input Format

  • The first line of input will contain a single integer T, denoting the number of test cases.
  • Each test case consists of multiple lines of input.
    • The first line of each test case contains a single integer N - denoting the length of arrays A and B.
    • The second line of each test case contains N space separated integers A_1, A_2, A_3, \dots A_N - denoting the array A.
    • The third line of each test case contains N space separated integers B_1, B_2, B_3, \dots B_N - denoting the array B.

Output Format

For each test case, output the minimum number of operations to make A and B equal or -1 if they cannot be made equal.

Constraints

  • 1 \leq T \leq 2 \cdot 10^4
  • 2 \leq N \leq 10^5
  • 1 \leq A_i, B_i \leq 10^9
  • Sum of N over all test cases do not exceed 10^5.

Sample 1:

Input
Output
3
2
1 2
2 1
3
1 1 2
2 2 1
3
4 6 8
5 7 6
1
-1
2

Explanation:

Test case 1: We can choose i = 1 and j = 2 and increment A_i and B_j by 1. Thus, both arrays become [2, 2] and are equal. We require only 1 operation to make these arrays equal. It can be proven that the arrays cannot be made equal in less than one operation.

Test case 2: Both the arrays cannot be made equal using any number of operations.

Test case 3: We perform 2 operations as follows:

  • Choose i = 1, j = 3: The arrays become A = [5, 6, 8] and B = [5, 7, 7].
  • Choose i = 2, j = 3: The arrays become A = [5, 7, 8] and B = [5, 7, 8].

Thus, both arrays can be made equal using 2 operations.



bool cmp(pii &a,pii&b){
    return a.second<b.second;
}

void solve() {

int n;
cin>>n;
vpi a,b;
for (int i = 0; i < n; i++)
{
    int x;
    cin>>x;
    a.push_back({x,i});
}
for (int i = 0; i < n; i++)
{
    int x;
    cin>>x;
    b.push_back({x,i});
}
sort(a.begin(),a.end());
sort(b.begin(),b.end());
int one=0,two=0;
int ans=0;
for (int i = 0; i < n; i++)
{
    int aa=a[i].first,bb=b[i].first;
    if(aa>bb)two+=aa-bb;
    else if(bb>aa)one+=bb-aa;

}
if(one!=two){cout<<-1<<endl;return;}

sort(a.begin(),a.end(),cmp);
sort(b.begin(),b.end(),cmp);

for (int i = 0; i < n; i++)
{
    ans+=abs(a[i].first-b[i].first);
}
cout<<ans/2<<endl;

}

Post a Comment

0 Comments