2
$\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$
  • $\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 Jul 11 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 Jul 11 at 11:34
0
$\begingroup$

Increasing all elements but one is equivalent to decrease only that element. Find minimum value m, now for each element x you need to find minumum number of subtractions to go from x to m (change-making problem), since you can use greedy algorithm for coins (1, 2, 5), you can solve this problem in O(n).

$\endgroup$
  • $\begingroup$ This will not always give the correct answer. Say the original array is [1, 5, 5]. Your algorithm would return 4 by decreasing the two 5 to 1. But one can actually do in 3 steps: decrease all of them to 0. $\endgroup$ – WhatsUp Oct 7 at 1:38
0
$\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, privacy policy and cookie policy

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