Categories
Mastering Development

What is the best algo for this array minimization problem?

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

Leave a Reply

Your email address will not be published. Required fields are marked *