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] – A`

, where _{new}[i]|`0 <= i <= n-1`

, n is size of `A[]`

and `A`

is the array with adjacent difference less that or equal to target._{new}[]

**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] – A`

for all index _{new}[i]|`i`

in the array,

`|A[i] – A`

should be as close to 0 as possible. Also, _{new}[i]|`|A[i] – A`

._{new}[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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include <stdio.h> #include <limits.h> #include <stdlib.h> #define M 100 int max(int x, int y) { return (x > y)? x : y; } int min(int x, int y) { return (x < y)? x : y; } // Find minimum adjustment cost of an array int minimalAdjustmentCost(int A[], int n, int target) { // T[i][j] stores minimal adjustment cost on changing A[i] to j int T[n][M + 1]; // do for each element of the array for (int i = 0; i < n; i++) { // replace A[i] to j and calculate minimal adjustment cost T[i][j] for (int j = 0; j <= M; j++) { // separately handle first element of array if (i == 0) { T[i][j] = abs(j - A[i]); } else { // initialize minimal adjustment cost to INT_MAX T[i][j] = INT_MAX; // consider all k such that k >= max(j - target, 0) and // k <= min(M, j + target) and take minimum int k = max(j - target, 0); while (k <= min(M, j + target)) { T[i][j] = min(T[i][j], T[i - 1][k] + abs(A[i] - j)); k++; } } } } // return minimum value from last row of T[][] table int result = INT_MAX; for (int j = 0; j <= M; j++) result = min(result, T[n - 1][j]); return result; } // main function int main(void) { int arr[] = { 55, 77, 52, 61, 39, 6, 25, 60, 49, 47 }; int target = 10; int n = sizeof(arr) / sizeof(arr[0]); printf("The minimal adjustment cost is %d", minimalAdjustmentCost(arr, n, target)); return 0; } |

`Output: `

The minimal adjustment cost is 75

## Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
class MinimalAdjustmentCost { private static final int M = 100; // Find minimum adjustment cost of an array public static int minimalAdjustmentCost(int[] A, int target) { // T[i][j] stores minimal adjustment cost on changing A[i] to j int[][] T = new int[A.length][M + 1]; // do for each element of the array for (int i = 0; i < A.length; i++) { // replace A[i] to j & calculate minimal adjustment cost T[i][j] for (int j = 0; j <= M; j++) { // separately handle first element of array if (i == 0) { T[i][j] = Math.abs(j - A[i]); } else { // initialize minimal adjustment cost to infinity T[i][j] = Integer.MAX_VALUE; // consider all k such that k >= max(j - target, 0) and // k <= min(M, j + target) and take minimum int k = Integer.max(j - target, 0); while (k <= Integer.min(M, j + target)) { T[i][j] = Integer.min(T[i][j], T[i - 1][k] + Math.abs(A[i] - j)); k++; } } } } // return minimum value from last row of T[][] table int result = Integer.MAX_VALUE; for (int j = 0; j <= M; j++) { result = Integer.min(result, T[A.length - 1][j]); } return result; } // main function public static void main(String[] args) { int[] A = { 55, 77, 52, 61, 39, 6, 25, 60, 49, 47 }; int target = 10; System.out.println("The minimal adjustment cost is " + minimalAdjustmentCost(A, target)); } } |

`Output: `

The minimal adjustment cost is 75

**Author:** Aditya Goel

**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

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

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

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.