I have an array say ‘A’ of size n having some numbers {a1, a2, …, an} not necessarily distinct.

I have to create another array B = {b1, b2, …, bn} which are distinct such that the value of

sum|ai – bi| over all i’s{i =1 to i =n} is minimized.

Basically I want to minimize sum of |ai – bi| over all i

What is the best algo for this?

I tried a greedy approach:

pseudocode:

```
for i = 0 to n-1{
if(a[i] not in b){
b[i] = a[i];}
else{
cnt = 1
assigned = false
do{
if(a[i]-cnt not in b){
b[i] = a[i]-cnt;
assigned = true}
elif(a[i]+cnt not in b){
b[i] = a[i]+cnt;
assigned = true}
else
cnt++
}while(assigned==false)
}//else
}//for loop
```

NOte:

‘n’ is an input variable.

the goal is to minimize sum of |ai – bi| over all i