Minimum number of transformation required to equalize an array

algorithm, arrays

Solution

You do not actually need to show the transformations but find the total number of such transformations required.

Incrementing all but one element is essentially the same as decreasing one element(for the purpose of equalizing all elements).

strategy: decrease all non-minimal elements until they equal the minimal element.

for eg. If the elements are {x1, x2, x3, x4...... xn} the number of transformations will be

let min = min{x1 .. xn}
for(int x : arr){
    // decrement x until x == m
}

Total number of transformations

sum(k = 1 to n)x(k)−n*min{x1,…,xn}

Sample run :

For array = {1,2,3}
sum(k=1 to n) x(k) = (1 + 2 + 3) = 6
n = 3
min = 1
num_transformations = 6 - 3*1 = 3 transformations

Problem

Given an array of n positive elements (including 0). We are allowed to perform only one transformation which is to increment each element of the list except one. What are the minimum number of transformation required to equalize this list? For example, `n = 3`, and the array being `1,2,3`. We need 3 such transformation as: `2,3,3 --> 3,3,4 --> 4,4,4`. For `n = 4` and the list being `1,3,2,4` the minimum number of transformation required is 6 Which is the best approach to solve this?

Original source