Determine Minimal Adjustment Cost of an Array

Write an algorithm to replace each element in an array of positive integers such that the difference between adjacent elements in the array is less than or equal to a given target. We need to minimize the adjustment cost which is the sum of differences between new and old values.

In other words, minimize ∑|A[i] – Anew[i]|, where 0 <= i <= n-1, n is size of A[] and Anew[] is the array with adjacent difference less that or equal to target.


 

For example,


Input: arr = [1, 3, 0, 3], target = 1
Output: Minimum adjustment cost is 3

One of the possible solutions is [2, 3, 2, 3]

 
Input: arr = [55, 77, 52, 61, 39, 6, 25, 60, 49, 47], target = 10
Output: Minimum adjustment cost is 75

One of the possible solutions is [55, 62, 52, 49, 39, 29, 30, 40, 49, 47]

 
Input: arr = [2, 3, 2, 3], target = 1
Output: Minimum adjustment cost is 0
All adjacent elements in the input array are already less than equal to given target

 

 
In order to minimize the adjustment cost ∑|A[i] – Anew[i]| for all index i in the array,
|A[i] – Anew[i]| should be as close to 0 as possible. Also, |A[i] – Anew[i+1] ]| <= Target.

 
We can use Dynamic Programming to solve this problem. Let T[i][j] defines minimal adjustment cost on changing A[i] to j, then the DP relation is defined by –

T[i][j] = min{T[i - 1][k]} + |j - A[i]|     for all k's such that |k - j| <= target

Here, 0 <= i < n and 0 <= j <= M where n is number of elements in the array. We have to consider all k such that max(j – target, 0) <= k <= min(M, j + target). Finally the minimum adjustment cost of the array will be min{T[n – 1][j]} for all 0 <= j <= M.

C

Download   Run Code

Output:

The minimal adjustment cost is 75

Java

Download   Run Code

Output:

The minimal adjustment cost is 75

 
Author: Aditya Goel

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding :)
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Abhishek
Guest

can you please expalin me as i’m finding difficulty understanding it.
dp[i][j] = min{dp[i – 1][k]} + |j – A[i]| for all k’s such that |k – j| <= target

Wolf
Guest

You can imagine this expression as a cone with 1 element at the bottom and a wide range at the top. If we have target=1 and j=3, its cone will look so:
1 |2 3 4| 5 …
––– |?| ––– …
It isn’t very wide because target=1, so k includes 2,3,4. If the target was 2 or more, k would be wider.

So if we use the example above for array [5,1] and target=1,
the first line will be
5-0, 5-1, 5-2, 5-3, 5-4, 5-5, 5-6, 5-7
=
5, 4, 3, 2, 1, 0, 1, 2
The second line will be:
min(5,4)+1-0, min(5,4,3)+1-1, min(4,3,2)+2-1, min(3,2,1)+3-1, min(2,1,0)+4-1, min(1,0,1)+5-1, min(0,1,2)+6-1, min(1,2)+7-1
=
5, 3, 3, 3, 3, 4, 5, 7
We take 3 as the answer and can choose any combination [5,1]=>([2,1] or [3,2] or [4,3] or [5,4])

Wolf
Guest

Ok, I see, the requirement is for adjacent elements, so the answer [4,3,2,1] for the array [6,3,0,1] and target = 1 is correct.
But if the requirement was for all elements, I think the solution could be easier, we would need to check only 2-3 numbers around the average (for example (6+3+0+1) / 4=2.5) instead of checking M numbers.