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 |
#include <stdio.h> #include <limits.h> #include <stdlib.h> // Assuming all elements of the array is less than constant 100 #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 minimal 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 for (int k = max(j - target, 0); k <= min(M, j + target); k++) { T[i][j] = min(T[i][j], T[i - 1][k] + abs(A[i] - j)); } } } } // 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

**Author:** Aditya Goel

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding :)

## Leave a Reply