No need for DP. Key insight is that adding to all colleagues except one is equivalent to taking away from only one colleague, with the modification of not "bottoming out" in cases where equality can be reached in fewer moves with bigger additions. For example [1, 5, 5] can reach equality in 4 add-2 moves at [9, 9, 9] ([1, 1, 1] if you take-away), but in only 3 total moves at [11, 11, 11] ([0, 0, 0] if you take-away). This is the reason for my offset param. The main logic gets the distance between each colleague and the minimum, and sums the multiples of 5, 2, and 1 necessary to equalize all colleagues at the minimum.

def equal(arr):
    def equalize(arr, offset):
        n_rounds = 0
        least = min(arr) - offset
        gaps = [x - least for x in arr]
        for choc in (5, 2, 1):
            n_rounds += sum(x // choc for x in gaps)
            gaps = [x % choc for x in gaps]
        return n_rounds
    return min(equalize(arr, x) for x in range(4))

Reference Table

[Edit] Notice how each column below the pivot (row1, col1 -> row2 col2 ->etc) contains the same pattern (0, 1, 1, 2, 2, 1, 2, 2, 3, 3, etc) . This pattern is the number of minimum steps to reduce the row value (arr[i]) to the column value (min).

Because of this in my final approach, I've decided to use only column 0 as my memoization array, called grid, since I can use index manipulation to fetch the result. For example:

1 . 4 . 2 2 3 7

if I wanted to find the minimum number of steps to go from 7 to 2, it would be 1 step of (-5), but instead of returning grid.at(7), i'll return grid.at(7 - min).

The cycle repeats 4 more times with each cycle decrementing the minimum value by 1, even below 0 - in which case row (7 - min) would still be in the grid.

A similar problem is TheCoinChangeProblem. If you can solve that one, then you'll see the process I found in this one.

Hi, no code, but the solution idea is very simple:

To give to all except one means just to take from this one. So, the idea is to find the sum of "take" operations needed to make each item equal to the minimum.

However, it could be that the minimum is not reachable or reachable in a non-optimal way, so we should also consider taking from the minimum itself.

But it is senseless to take from the minimum the maximum piece or even more (it is obviously non-optimal — we will need to do the same with the rest as well). Therefore, we should consider possible alignments to min, min - 1, min - 2, min - 3, and min - 4.

Finally, just find the minimum of the sum of operations for each corresponding target.

Hello, here is my solution. It didn't passed the last test case, but it's a good path of understanding and how you can implement yours one.

int min (int a, int b) {
    return a > b ? b : a;
}


int rounds(int ele, int target, int** memo) {
    if (ele < target) return INT_MAX; 
    
    if (ele == target) return 0; 

    if (memo[ele][target] != -1) return memo[ele][target];
    
    int result = 1 + min(min(rounds(ele - 5, target, memo), 
                            rounds(ele - 2, target, memo)), 
                        rounds(ele - 1, target, memo));

    return memo[ele][target] = result;
}


int equal(int n, int* arr) {
    int MIN = INT_MAX;
    int max = INT_MIN;

    /**
     * We will find the max element
     * as we need to create our memoization
     * table
     */

    /**
     * First of all find the minimum
     * value in the array so we can start 
     * reducing the values to matche it
     */
    for (int x = 0; x < n; x++) {
        if (arr[x] < MIN) MIN = arr[x];
        if (arr[x] > max) max = arr[x];
    }
    /**
     * Create the memoization
     * table to save our computed results 
     * memo[element][target]
     */
    int** memo = calloc(max + 1, sizeof(int*));
    for (int x = 0; x <= max; x++) {
        memo[x] = calloc(max + 1, sizeof(int));
    }
    for (int x = 0; x <= max; x++) {
        for (int l = 0; l <= MIN; l++) {
            memo[x][l] = -1;
        }
    }
    /**
     * Now starting cutting the array
     * to matche the minimu value
     */
    int min_rounds = 0;
    int min_rounds_zero = 0;
    for (int x = 0; x < n; x++) {
        min_rounds += rounds(arr[x], MIN, memo);
        min_rounds_zero += rounds(arr[x], 0, memo);
    }

    for (int x = 0; x <= max; x++) {
        free(memo[x]);
    }
    free(memo);
    return min(min_rounds, min_rounds_zero);
}

Feel absolutely robbed on this one, this is an exercise that seemingly punishes efficiency. It should be comparing output AND operations, as I have completed 'Sample Test case 0' in the following operations: - 933 - 923 - 948 - 979 - 895 `

Iteration: 933, Largest: 4657, Smallest: 4657, Arr: 4657, ...n