We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Equal
  5. Discussions

Equal

Sort by

recency

|

459 Discussions

|

  • dshchehlov
     + 0 comments

    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.

  • michaelres3344
     + 0 comments

    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);
}

  • kallum_parr
     + 1 comment

    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

  • fourdollars
     + 2 comments

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

    1

    4

    2 2 7 7

  • ssdunera
     + 2 comments
    public static int equal(List<Integer> arr) {
        // Store all the possibilities
        int[] possibilities = new int[5];
        // Start with the minimum element
        int minimum = Collections.min(arr);
        for (int i = 0; i < possibilities.length; i++) {
            for (int k : arr) {
                int diff = k - minimum;
                int stepsRequired = diff / 5 + (diff % 5) / 2 + ((diff % 5) % 2) / 1;
                possibilities[i] += stepsRequired;
            }
            minimum--;
        }
        // Return the minimum number out of all the possibilities
        return Arrays.stream(possibilities).min().getAsInt();
    }