3
$\begingroup$

I'm stuck in this problem and I would need some help:

Given an array arr, in each step, 1, 2 or 5 units have to be incremented to all but one item of the array. The goal is to find the minimum number of steps to all items to be equal.

First example

arr = [1, 1, 5]

1) [1 (+2), 1 (+2), 5] = [3, 3, 5]
2) [3 (+2), 3 (+2), 5] = [5, 5, 5]

Solution: 2 steps


Second example

arr = [2, 2, 3, 7]

1) [2 (+1), 2 (+1), 3, 7 (+1)] = [3, 3, 3, 8]
2) [3 (+5), 3 (+5), 3 (+5), 8] = [8, 8, 8, 8]

Solution: 2 steps


I have tried some things but I'm really stuck.

I consider a base case when all items are already equal. In another case, I try to find all the possible solutions by incrementing 1, 2 and 5 to every item but one in the array:

def equal(arr):

    if (allElementsIdentical(arr)):
        return 0

    min = sys.maxsize
    for i in [1, 2, 5]:
        for j in range(len(arr)):

            #Increment all items by "i", except item at index "j"
            newArr = arr.copy()
            for k in range(j):
                newArr[k] += i
            for k in range(j + 1, len(newArr)):
                newArr[k] += i

            movements = 1 + equal(newArr)
            if movements < min:
                min = movements
    return min

This solution doesn't work because recursion never ends. E.g.

[1, 1, 5] -> [1, 2, 6] -> [1, 3, 7] -> [1, 4, 8] -> [1, 5, 9] -> ...

Is it my initial approach correct? How can I break it down in subproblems?

$\endgroup$
2
  • $\begingroup$ Here's a hint: The final values don't matter, only the fact that they are equal. Think of what happens in terms of the relative differences of the elements in the array. Adding $i$ to all but one elements is equivalent to to decreasing $i$ from exactly one element -- the one you wouldn't add to. For example, in the first case your solution is equivalent to subtracting twice 2 from 5 to obtain [1,1,1]. $\endgroup$
    – Vincenzo
    Commented Jul 11, 2019 at 11:28
  • $\begingroup$ Thank you, you are right. In the second case, subtracting 1 from 3 and 5 from 7, you obtain [2, 2, 2, 2] in two steps. I'm going to try to code it. $\endgroup$
    – Héctor
    Commented Jul 11, 2019 at 11:34

1 Answer 1

1
$\begingroup$

The main idea is as in the answer by @izanbf1803.

However, there is a detail: after you find the minimum value m, you should go through the array again, keeping in mind that m, m - 1 and m - 2 could all be your final target. After getting the total number of steps for all three of them, just return the smallest one.

For example, if the array is [0, 0, 0], then the best final target is m = 0;

if the array is [1, 5, 5], then the best final target is m - 1 = 0;

if the array is [2, 5, 5], then the best final target is m - 2 = 0.


But why only these three possibilities? The reason is as follows.

Let f(n) be the number of steps required to decrease a number by n. It's easy to show by induction that:

  • f(5k) = k
  • f(5k + 1) = k + 1
  • f(5k + 2) = k + 1
  • f(5k + 3) = k + 2
  • f(5k + 4) = k + 2

and to continue:

  • f(5k + 5) = k + 1
  • f(5k + 6) = k + 2
  • f(5k + 7) = k + 2
  • etc.

from which one sees that f(n) <= f(n + 3).

If a number t is chosen as the final target, then the total minimum number of steps is just the sum of f(x - t) for all x in the array. Hence choosing any number t <= m - 3 as final target would be pointless, since t + 3 would be a better choice.

Thus the final algorithm goes like this:


Input: array arr

Output: minimum number of steps to make all numbers equal

Define a constant array c = [0, 1, 1, 2, 2].
Let m = minimum value in the array arr.
Let s = 0, s1 = 0 and s2 = 0.
For every element x in arr:
    Let y = x - m, y1 = y + 1 and y2 = y + 2
    Add [y / 5] + c[y mod 5] to s.
    Add [y1 / 5] + c[y1 mod 5] to s1.
    Add [y2 / 5] + c[y2 mod 5] to s2.
End For.
Return min(s, s1, s2).
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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