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

|

458 Discussions

|

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

  • mah_shamim
     + 0 comments

    Problem Explanation:

    Given an array of integers, you can perform the following operations any number of times: - Subtract 1 from any element. - Subtract 2 from any element. - Subtract 5 from any element.

    The goal is to determine the minimum number of operations required to make all the elements in the array equal.

    Solution Approach:

    1. Find the Minimum Element: Identify the smallest element in the array since this will guide us on how much we need to reduce the other elements.
    2. Consider Different Targets: To minimize operations, consider making all elements equal to min_element, min_element-1, min_element-2, min_element-3, and min_element-4. This is because these slight variations might help avoid some larger reductions.
    3. Calculate Operations: For each of these target values, calculate the total number of operations required to reduce all elements in the array to that target.
    4. Choose the Best Option: The answer will be the minimum number of operations required among all these target values.

    PHP Implementation:

    Here is the implementation in PHP:

    <?php

function minOperations($arr, $target) {
    $operations = 0;
    foreach ($arr as $value) {
        $diff = $value - $target;
        $operations += intdiv($diff, 5);
        $diff %= 5;
        $operations += intdiv($diff, 2);
        $diff %= 2;
        $operations += $diff;
    }
    return $operations;
}

function equal($arr) {
    $min_value = min($arr);
    $min_operations = PHP_INT_MAX;

    // Check reducing to min_value, min_value-1, ..., min_value-4
    for ($i = 0; $i < 5; $i++) {
        $target = $min_value - $i;
        $operations = minOperations($arr, $target);
        if ($operations < $min_operations) {
            $min_operations = $operations;
        }
    }

    return $min_operations;
}

// Test cases
$arr1 = [2, 2, 3, 7];
$arr2 = [10, 7, 12];
$arr3 = [1, 1, 1, 1];

echo equal($arr1) . "\n"; // Output: 2
echo equal($arr2) . "\n"; // Output: 3
echo equal($arr3) . "\n"; // Output: 0
?>

    Explanation of the Code:

    1. minOperations Function: This function calculates the number of operations needed to reduce all elements in the array to a specified target.
      • It uses integer division and modulo operations to determine how many steps of 5, 2, and 1 are needed.
    2. equal Function: This function iterates over possible target values (from min_value to min_value-4) and uses the minOperations function to determine the minimum number of operations required.
    3. Test Cases: The test cases check for various scenarios to ensure the solution works correctly.

    This implementation ensures that all possible target reductions are considered, and the minimum number of operations required to make all elements in the array equal is found.