I could not understand the 3rd step … :(…Can somebody please explain??
Let the SORTED ARRAY OF NEGATIVE INTEGERS be ARR[-a1,-a2,-a3,…,an] ,where (-a1<-a2<-a3<…<-an)
Take an Example:
Let X=2 , BE THE COST OF FIRST TYPE OPERATION…
Now, You have to keep increasing the Array Elements and stop as soon as -a3 becomes ZERO… (INCREASING THE ARRAY ELEMENTS BEYOND THIS WILL NOT BENIFIT YOU.!!)
… ALSO , NOTE : When -a3 becomes ZERO , all the successive NEGATIVE INTEGERS after -a3 also becomes >= ZERO … This is the main Step …
Hence -> Cost for FIRST type operation -> c1 = 2*a3;
Now You Also have to make the remaining -ve Integers >= 0
->SUM OF LEFTOVER -ve ELEMENTS = -a1-a2+(2*a3) … (Since both -a1 & -a2 is increased a3 times now … )
Hence -> Cost of SECOND type operation -> c2 = a1 + a2 - 2*a3 … (to make the LEFTOVER -ve ELEMENTS = ZERO)
->TOTAL COST = (c1+c2) = 2a3 + a1+a2-2a3 = a1+a2 … (ie : SUM OF THE LAST Xth ELEMENT if you make them +ve while Inserting !!)
Hope it helped !