Making all integers in an array same using minimum steps

In past rounds of both topcoder and codeforces, same problem showed up with slight variations. In generic terms, we had to make all integers in an array same, using minimum number of steps, where a single step is incrementing or decrementing a single element of the array by a constant integer, say ‘d’.

Solution:

We need to figure out median of the sorted array, set that as the target, and make all elements equal to this target. This will ensure minimum increments/decrements. When the number of elements in array “N” are odd, median is (N/2)th element of the array. If N is even, we have two medians, (N/2)th and (N/2)+1th element. We can choose any integer between these two medians (inclusive) as the target (given that selected integer is equal to other elements modulo ‘d’).

Remember that in order for a solution to exist, all elements in the array need to be equal modulo “d”. Because otherwise, no matter what number of increments/decrements your perform, integers can’t be equalized.

Explanation:

Why select median element as the target to make all other elements equal to?

Lets take an example: A = [2, 4, 5, 8, 9, 15, 35], d = 1

Here, median element is N/2 = 7/2 = 3rd element = 8 (0 indexed).

Lets start by deciding not to use median element as the target. Lets select another integer, ‘x’, as the target, which is not the median. It can be in either direction of the median, left, or right. In our example, let x = 4. Now lets say that the number of increments/decrements we had to perform to make all elements in given array equal to x, is ‘c’, the cost. Lets move our chosen target x closer to median by an element by incrementing by d, so that we now have one more element to the left, and one less on the other side. In our example case, let our new x = ‘5’. Now we have one more element to the left of our target, and one less to the right. Now in order to equalize all elements in our new array, which was equalized to our previous target of ‘4’, notice that we will have to add ‘d’ to all the elements to left of our target, and reduce ‘d’ from all elements to the right. Since number of elements to the left is 2, and there are 4 elements to the right. our cost ‘c’ is reduced. We can keep on going like this, till we reach the median as our target ‘x’. Once we have chosen median as our target ‘x’, we obtain an optimal cost ‘c’. Going either to left or right of it, only increases our cost.

Be Sociable, Share!

2 thoughts on “Making all integers in an array same using minimum steps

  1. Hey can you tell me the algorithm if we can only add a constant positive integer without any substraction operation with the above problem???

Leave a Reply