# 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

Output:

The minimal adjustment cost is 75

## Java

Output:

The minimal adjustment cost is 75

(1 votes, average: 5.00 out of 5)

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 :)

Subscribe
Notify of
Guest
Abhishek

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

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])

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.