CODEWITHSUNDEEP
algorithm
Rishabh Agarwal jain
Rishabh Agarwal jain

Reputation: 117

Array manipulation (Minimum deletions required)

Given a array on positive integers, I can decrease any element by any amount such that all the remaining non zero elements are equal.

I have to find min value which is sum of all the decrease occurred.

EX: 1 1 1 1 2
Ans: 1 ( decrease only last element by 1).

EX: 25 23 1 2
Ans: 5 ( one possible way is to decrease 25 to 23, and decrease 1 to 0, decrease 2 to 0 . After all decrease operations array is 23 23 0 0 which has all non zero element equal.)

I tried the approach of finding the minimum in array and then equating all others elements to that. But that approach fails the second case.Any help on this is highly appreciated.

Upvotes: 1

Views: 187

Answers (2)

Prodigy
Prodigy

Reputation: 59

Your approach sounds good but has major pitfalls and it doesn't work all the time. It would work if there is no option to equate the number to zero. In this problem scenario, for each candidate you should calculate the sum of diffs obtained by equating all bigger numbers to this candidate and all smaller numbers to zero, and see which candidate has smallest sum of diffs.

Here's the algo...

  1. Base case: If array has negative numbers, throw an error or return -1 (error code).
  2. Sort: Sort the array - O(n log n)
  3. Left Sum: From left to right, for each position calculate cumulative sum of all numbers on the left. - O(n)
  4. Right Sum: From right to left, for each position calculate cumulative sum of all elements on the right. - O(n)
  5. Minimum difference: For each position, assume this is the minimum number you equate all non-zero elements to. All smaller numbers should be reduced to zero. So, take the left sum corresponding to this position. All larger numbers should be reduced to this number. So, calculate what is excess and add it to the left sum. If the resultant sum is less than current minimum, update current minimum. - O(n)

The overall complexity is O(n log n) and here's some code...

private static int getMinimumDifference(int[] arr) {
    int n = arr.length;

    for (int i = 0; i < n; i++) {
        if (arr[i] < 0) {
            return -1;
        }
    }
    if (n == 1)
        return 0;

    int left[] = new int[n];
    int right[] = new int[n];

    Arrays.sort(arr);

    int tempSum = 0;
    for (int i = 0; i < n; i++) {
        left[i] = tempSum;
        tempSum += arr[i];
    }

    tempSum = 0;
    for (int i = n - 1; i >= 0; i--) {
        right[i] = tempSum;
        tempSum += arr[i];
    }

    int minDiff = tempSum, index = -1;
    for (int i = 0; i < n; i++) {
        int diff = 0;
        diff += left[i]; // All numbers on the left reduced to 0
        diff += right[i] - (arr[i] * (n - i - 1)); // All numbers on the right reduced to arr[i]
        if (diff < minDiff) {
            minDiff = diff;
            index = i;
        }
    }
    System.out.println("Minimum difference is " + minDiff + " and all numbers should be " + (index >= 0 ? arr[index] : "unknown"));
    return minDiff;
}

Upvotes: 0

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

Your approach is good, but you need to consider more choices for the target value.

It could be any of the values in the array, so simply try all of them in turn. This will be an O(n^2) algorithm.

If you want to go faster, you could sort the entries first. You can then easily compute the cost of each target value in turn (because you know you need to reduce all elements before the current position to 0, and all elements after the current position to the target value, so the total cost is the sum of all elements minus the current value times the number of elements beyond the current position)

Upvotes: 2

Related Questions