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;

}