Find Maximum Difference Between any Two Pairs By Following Operations Optimally
Given an array X[] of length N along with A and B. You can apply below type of operations:
- Operation 1: Choose two different indices, delete elements at both indices and insert the sum of them in X[]. This operation decrements A by 1.
- Operation 2: Choose two different indices, delete elements at both indices and insert the difference of them in X[]. This operation decrements B by 1.
Considered that after making optimal number of operations, we get array Y[].
Then your task is to output the maximum difference between the maximum and minimum element among all the possible Y[] that can be formed using given operation under the cost of A and B.
Note: It is not necessary to use all cost A and B.
Examples:
Input: N = 6, A = 1, B = 2, X[] = {8, -1, -4, 2, 6, -3}
Output: 23
Explanation: The operations are performed as:
- First Operation: Choose i = 4 and j = 6, So that A4 = 2 and A6 = -3. Difference between them is: 2 – (-3) = 5. Add difference into X[] and delete both elements. So updated X[] = {8, -1, -4, 6, 5}. This operation decrements B by 1. Now, A = 1 and B = 2 – 1 = 1.
- Second Operation: Choose i = 1 and j = 5, So that A1 = 8 and A5 = 5. Sum of them is: 8 + 5 = 13. Add sum into X[] and delete both elements. So updated X[] = {-1, -4, 6, 13}. This operation decrements A by 1. Now, A = 0 and B = 1.
- Third Operation: Choose i = 2 and j = 3, So that A2 = -4 and A3 = 6. Difference between them is: -4 – (6) = -10. Add difference into X[] and delete both elements. So updated X[] = {-1, -10, 13}. This costs decrements B by 1. Now, A = 0 and B = 0.
Now, In X[] max element and minimum element of X[] are 13 and -10 respectively. The difference between them is 13 – (-10) = 23. Which is maximum among all the possible arrays formed by given operation. Thus, output is 23.
Input: N = 3, A = 0, B = 0, X[] = {3, -1, 0}
Output: 4
Explanation: As A and B are initially zero. We can’t make any type of given operation, As the value of A or B must be greater than or equal to 1. Thus, the maximum possible difference between maximum and minimum value will be: 3 – (-1) = 4.
Approach: Follow below idea to solve the above problem:
Main logic: To maximize the difference, we have two straightforward options:
- Either increase the maximum element in the X[] by adding a number (raising the maximum), or decrease the minimum element by subtracting a number (lowering the minimum).
Before any operations, the result (denoted as Res) can be expressed as the difference between the maximum (Max_elem) and minimum (Min_elem) elements:
- To increase the maximum element, we add X: (Max_elem + X) – Min_elem = Res + X.
- To decrease the minimum element, we subtract X: Max_elem – (Min_elem – X) = Max_elem – Min_elem + X = Res + X. If X is negative, we add it to the minimum element to lower it, which simplifies to: Max_elem – (Min_elem + (-X)) = Max_elem – (Min_elem – x) = Res + X.
- This leads us to the third observation: the number’s parity is inconsequential. In every scenario, we add the absolute value of X to the result. This process continues for (A + B) iterations or until the array is exhausted, capped at min(A+B, N-2) iterations. We use N-2 because X[0] and X[n-1] are the minimum and maximum elements initially used to calculate Res.
Example:
X[] = {-5, -4, 3, 7}
At current, the difference is 7- (-5) = 12. Let A = 1, B = 0, obviously you could have just added 3 to 7 thinking its a positive number and move on . But when you grow serious, you realize that instead of adding 3 to 7, (which makes net difference ((7+3) – (-5) = 15), you could have added -4 to -5 to get a more difference (7 – (-5-4) = 16). So, what we realized, we need to deal with absolute value of numbers instead of numbers itself.
Steps were taken to solve the problem:
- Sort X[].
- Declare a variable let say Res and store the initial difference between max and min element of X[].
- If (A == 0 and B == 0)
- Output value store in Res.
- Declare a variable let say Ops and initialize it with the total available cost. Formally, A+B
- Run a loop for i = 1 to i < N-1 and make all the elements positive.
- Sort X[], except first and last element.
- Run a loop for i = N – 2 to i>0 and follow below mentioned steps under the scope of loop:
- If (Ops == 0)
- Break
- Else
- Res += X[i]
- Ops—
- If (Ops == 0)
- Output the value stored in Res.
Below is the implementation of the above idea:
C++
// code by flutterfly #include <iostream> #include <algorithm> #include <vector> using namespace std; // Function to output maximum difference void Max_diff( long long N, long long A, long long B, vector< long long >& X) { // Sorting X[] using inbuilt function sort(X.begin(), X.end()); // Max difference in the initial array long long res = X[N - 1] - X[0]; // Variable to hold the cumulative sum of both costs long long ops = A + B; // If both costs are zero // Then output the initial difference if (A == 0 && B == 0) { cout << res << endl; } // Else implementing the discussed approach else { // Looping over each element and changing them // into positive elements for ( int i = 1; i < N - 1; i++) { X[i] = abs (X[i]); } // Sorting X sort(X.begin() + 1, X.end() - 1); // Calculating the difference for ( int i = N - 2; i > 0; i--) { if (ops == 0) { break ; } else { res += X[i]; ops--; } } // Printing out the max difference cout << res << endl; } } // Driver Function int main() { // Inputs long long N = 7; long long A = 6; long long B = 6; vector< long long > X = { -2, -4, 2, -2, -3, -1, -1 }; // Function call Max_diff(N, A, B, X); return 0; } |
Java
// Java code to implement the approach import java.util.*; // Driver Class public class Main { // Driver Function public static void main(String[] args) { // Inputs long N = 7 ; long A = 6 ; long B = 6 ; long [] X = { - 2 , - 4 , 2 , - 2 , - 3 , - 1 , - 1 }; // Function_call Max_diff(N, A, B, X); } // Method to output maximum difference public static void Max_diff( long N, long A, long B, long [] X) { // Sorting X[] using inbuilt function Arrays.sort(X); // Max difference in initial array long res = X[( int )N - 1 ] - X[ 0 ]; // Variable to hold the cumulative sum of // both costs long ops = A + B; // If both costs are zero // Then output initial difference if (A == 0 && B == 0 ) { System.out.println(res); } // Else implementing the discussed approach else { // Looping over each element and changing them // into positive elements for ( int i = 1 ; i < N - 1 ; i++) { X[i] = Math.abs(X[i]); } // Sorting X Arrays.sort(X, 1 , ( int )N - 1 ); // Calculating the difference for ( int i = ( int )N - 2 ; i > 0 ; i--) { if (ops == 0 ) { break ; } else { res += X[i]; ops--; } } // Printing out the max difference System.out.println(res); } } } |
Python
# code by flutterfly # Python code to implement the approach # Method to output maximum difference def max_diff(N, A, B, X): # Sorting X[] using inbuilt function X.sort() # Max difference in the initial array res = X[N - 1 ] - X[ 0 ] # Variable to hold the cumulative sum of both costs ops = A + B # If both costs are zero, then output initial difference if A = = 0 and B = = 0 : print (res) else : # Looping over each element and changing them into positive elements for i in range ( 1 , N - 1 ): X[i] = abs (X[i]) # Sorting X X[ 1 :N - 1 ] = sorted (X[ 1 :N - 1 ]) # Calculating the difference for i in range (N - 2 , 0 , - 1 ): if ops = = 0 : break else : res + = X[i] ops - = 1 # Printing out the max difference print (res) # Driver Function if __name__ = = "__main__" : # Inputs N = 7 A = 6 B = 6 X = [ - 2 , - 4 , 2 , - 2 , - 3 , - 1 , - 1 ] # Function call max_diff(N, A, B, X) |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { // Function to output maximum difference static void Max_diff( long N, long A, long B, List< long > X) { // Sorting X[] using inbuilt function X.Sort(); // Max difference in the initial array long res = X[( int )N - 1] - X[0]; // Variable to hold the cumulative sum of both costs long ops = A + B; // If both costs are zero // Then output the initial difference if (A == 0 && B == 0) { Console.WriteLine(res); } // Else implementing the discussed approach else { // Looping over each element and changing them // into positive elements for ( int i = 1; i < N - 1; i++) { X[i] = Math.Abs(X[i]); } // Sorting X X.Sort(1, ( int )N - 2, Comparer< long >.Default); // Calculating the difference for ( int i = ( int )N - 2; i > 0; i--) { if (ops == 0) { break ; } else { res += X[i]; ops--; } } // Printing out the max difference Console.WriteLine(res); } } // Driver Function static void Main() { // Inputs long N = 7; long A = 6; long B = 6; List< long > X = new List< long >{ -2, -4, 2, -2, -3, -1, -1 }; // Function call Max_diff(N, A, B, X); } } |
Javascript
// Function to output maximum difference function maxDiff(N, A, B, X) { // Sorting X[] using inbuilt function X.sort((a, b) => a - b); // Max difference in the initial array let res = X[N - 1] - X[0]; // Variable to hold the cumulative sum of both costs let ops = A + B; // If both costs are zero, then output initial difference if (A === 0 && B === 0) { console.log(res); } else { // Looping over each element and changing them into positive elements for (let i = 1; i < N - 1; i++) { X[i] = Math.abs(X[i]); } // Sorting X X.slice(1, N - 1).sort((a, b) => a - b); // Calculating the difference for (let i = N - 2; i > 0; i--) { if (ops === 0) { break ; } else { res += X[i]; ops -= 1; } } // Printing out the max difference console.log(res); } } // Driver Function // Inputs const N = 7; const A = 6; const B = 6; const X = [-2, -4, 2, -2, -3, -1, -1]; // Function call maxDiff(N, A, B, X); |
15
Time Complexity: O(N*logN), As Sorting is performed.
Auxiliary Space: O(1)