2
$\begingroup$

Recently the following problem was posed in a private coding competition at my workplace:

An array $A$ is given that has only positive integers in it. The objective is to equalize the array in minimum possible steps. In every step all but one element are incremented by a fixed step size. The possible step sizes are given in another array $D$.For example, if $A=\{2,2,3,7\}$ and $D=\{1,2,5\}$ we can equalize $A$ in two steps, first adding $A=\{5,5,5,0\}$ to get $A=\{7,7,8,7\}$ and then adding $\{1,1,0,1\}$ to get $A=\{8,8,8,8\}$.

In discussion forums it was suggested to repeatedly find the difference of the smallest and largest elements and then greedily increment all but the largest element by this amount. An implementation using this strategy passed all test cases. However I'm unable to see how this strategy will indeed result in the smallest number of steps.

$\endgroup$
3
$\begingroup$

Actually I am not sure the greedy solution will always give the best solution?

Recall that the change making problem does not work for certain denominations in a greedy way. For example with denominations $1,3,4$ and a goal of $6$ the greedy solution will give $4,1,1$ whereas the optimal solution is $3,3$.

This can be translated into your problem. Start with array $A=[0,6]$ and steps $D=\{1,3,4\}$. Now your greedy solution seems to behave like change making. I am not certain about this, however, as your description does not precisely say by which amount the numbers are incremented. Perhaps your algorithm chooses $[0,6] \to [4,6] \to [7,6] \to [7,7]$ (which is also wrong, anyway).

$\endgroup$
  • $\begingroup$ Thanks Hendrik. So my strategy is clearly sub-optimal. I'm not able to come up with any other strategy for solving the problem. In fact i'm not sure a solution would always exist. I'll ask separate questions for these. $\endgroup$ – farhanhubble May 19 '16 at 5:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.