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

I found something weird. If your program passed the problem, what is the output for this input?

1

4

2 2 7 7