Question

You are given two integer arrays a and b of the same length. Let's define the difference between a and b as the sum of absolute differences of corresponding elements:

difference = |a[0] - b[0]| + |a[1] - b[1]| + ... + |a[a.length - 1] - b[b.length - 1]|

You can replace one element of a with any other element of a. Your task is to return the minimum possible difference between a and b that can be achieved by performing at most one such replacement on a. You can also choose to leave the array intact.

Example:

For a = [1, 3, 5] and b = [5, 3, 1], the output should be minDiffOfArrays(a, b) = 4.
If we leave the array a intact, the difference is |1 - 5| + |3 - 3| + |5 - 1| = 8;
If we replace a[0] with a[1], we get a = [3, 3, 5] and the difference is |3 - 5| + |3 - 3| + |5 - 1| = 6;
If we replace a[0] with a[2], we get a = [5, 3, 5] and the difference is |5 - 5| + |3 - 3| + |5 - 1| = 4;
If we replace a[1] with a[0], we get a = [1, 1, 5] and the difference is |1 - 5| + |1 - 3| + |5 - 1| = 10;
If we replace a[1] with a[2], we get a = [1, 5, 5] and the difference is |1 - 5| + |5 - 3| + |5 - 1| = 10;
If we replace a[2] with a[0], we get a = [1, 3, 1] and the difference is |1 - 5| + |3 - 3| + |1 - 1| = 4;
If we replace a[2] with a[1], we get a = [1, 3, 3] and the difference is |1 - 5| + |3 - 3| + |3 - 1| = 6;
The final answer is 4, since it's the minimum possible difference.

Answer 1

In this question task is to return the min possible value of sum of absolute of difference of a[i] and b[i]. the condition imposed is that at max one value of a[i] can be replaced with other a array's value.

Lets suppose absval is sum of absolute of difference of a[i] and b[i] at the beginning.

So to solve this optimally choose two index of array a such that replacing (index i )value with (index j) value will give us max possible decrement in absval.

Lets call that max possible achievable decrement as diff.

Now for each index(i) of array a look for value of array a index (j) such that replacing a[i] with a[j] give max possible decrement in absval for that index. to do this store value of array a in c and d array.

sort them now use lower_bound function in each of c and d to find closest element to b[i] in array a which will give us most optimal solution.

use this approach for each index and will find maxpossible decrement that can be achieved in initial absval.

final answeer will be (absval-diff).

Code for above logic is given below

*lower_bound (a,x) return first positon in array a which has value >=x(nearest greater value to x)

*lower_bound (a,x) return first positon in array a which has value <=x(nearest smaller value to x)

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
int a[n],b[n],c[n],d[n];
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++)
cin>>b[i];
for(int i=0;i<n;i++)
{
c[i]=a[i];
d[i]=a[i];
}
sort(c,c+n);
sort(d,d+n,greater<>());
int absval=0;
for(int i=0;i<n;i++)
absval+=abs(a[i]-b[i]);
int maxdiff=0;
for(int i=0;i<n;i++)
{
  int index1 = lower_bound(c,c+n,b[i]) -c;//closest value to b[i] in a in right side
  int index2 = lower_bound(d,d+n,b[i]) -d;//closest value to b[i] in a in left side
  int diff1=0,diff2=0;
  if(index1<n)
  diff1 = abs(a[i]-b[i]) - abs(c[index1]-b[i]); 
  if(index2<n)
  diff2 = abs(a[i]-b[i]) - abs(c[index2]-b[i]);
  maxdiff = max(0,max(diff1,diff2));//max possible decrement 
}
cout<<absval-maxdiff;
}

Output and program snapshots.